Implementación y evaluación de un algoritmo de clustering en un estimador de ancho de banda disponible

Este proyecto está enmarcado dentro de la línea de investigación en Telemática del grupo de investigación en tecnologías de la información de la UNAB se planteo como objetivo implementar en lenguaje C un algoritmo de clustering en el estimador de ancho de banda Traceband y evaluar impacto del algori...

Full description

Autores:
Salcedo Morillo, Dixon David
Tipo de recurso:
Fecha de publicación:
2011
Institución:
Universidad Autónoma de Bucaramanga - UNAB
Repositorio:
Repositorio UNAB
Idioma:
spa
OAI Identifier:
oai:repository.unab.edu.co:20.500.12749/3467
Acceso en línea:
http://hdl.handle.net/20.500.12749/3467
Palabra clave:
Clustering technique
Network infrastructure
Traceband bandwidth
Free software
Systems engineer
Broadband communication systems
Algorithms
Computers
Research
Ingeniería de sistemas
Sistemas de comunicación de banda ancha
Algoritmos
Computadores
Investigaciones
Técnica de clustering
Infraestructura de red
Ancho de banda Traceband
Software libre
Rights
openAccess
License
http://creativecommons.org/licenses/by-nc-nd/2.5/co/
id UNAB2_d1369de9d7845db98e87291df6cecdc8
oai_identifier_str oai:repository.unab.edu.co:20.500.12749/3467
network_acronym_str UNAB2
network_name_str Repositorio UNAB
repository_id_str
dc.title.spa.fl_str_mv Implementación y evaluación de un algoritmo de clustering en un estimador de ancho de banda disponible
dc.title.translated.eng.fl_str_mv Implementation and evaluation of a clustering algorithm in an available bandwidth estimator
title Implementación y evaluación de un algoritmo de clustering en un estimador de ancho de banda disponible
spellingShingle Implementación y evaluación de un algoritmo de clustering en un estimador de ancho de banda disponible
Clustering technique
Network infrastructure
Traceband bandwidth
Free software
Systems engineer
Broadband communication systems
Algorithms
Computers
Research
Ingeniería de sistemas
Sistemas de comunicación de banda ancha
Algoritmos
Computadores
Investigaciones
Técnica de clustering
Infraestructura de red
Ancho de banda Traceband
Software libre
title_short Implementación y evaluación de un algoritmo de clustering en un estimador de ancho de banda disponible
title_full Implementación y evaluación de un algoritmo de clustering en un estimador de ancho de banda disponible
title_fullStr Implementación y evaluación de un algoritmo de clustering en un estimador de ancho de banda disponible
title_full_unstemmed Implementación y evaluación de un algoritmo de clustering en un estimador de ancho de banda disponible
title_sort Implementación y evaluación de un algoritmo de clustering en un estimador de ancho de banda disponible
dc.creator.fl_str_mv Salcedo Morillo, Dixon David
dc.contributor.advisor.spa.fl_str_mv Guerrero, Cesar D.
dc.contributor.author.spa.fl_str_mv Salcedo Morillo, Dixon David
dc.contributor.cvlac.spa.fl_str_mv Guerrero, Cesar D. [0000809357]
dc.contributor.googlescholar.spa.fl_str_mv Guerrero, Cesar D. [_YgBOOcAAAAJ]
dc.contributor.orcid.spa.fl_str_mv Guerrero, Cesar D. [0000-0002-3286-6226]
dc.contributor.scopus.spa.fl_str_mv Guerrero, Cesar D. [23094317500]
dc.contributor.researchgate.spa.fl_str_mv Guerrero, Cesar D. [Cesar-Guerrero-2]
dc.contributor.publons.spa.fl_str_mv Guerrero, Cesar D. [cesar-d-guerrero]
dc.contributor.linkedin.none.fl_str_mv Guerrero, Cesar D. [cguerrer]
dc.subject.keywords.eng.fl_str_mv Clustering technique
Network infrastructure
Traceband bandwidth
Free software
Systems engineer
Broadband communication systems
Algorithms
Computers
Research
topic Clustering technique
Network infrastructure
Traceband bandwidth
Free software
Systems engineer
Broadband communication systems
Algorithms
Computers
Research
Ingeniería de sistemas
Sistemas de comunicación de banda ancha
Algoritmos
Computadores
Investigaciones
Técnica de clustering
Infraestructura de red
Ancho de banda Traceband
Software libre
dc.subject.lemb.spa.fl_str_mv Ingeniería de sistemas
Sistemas de comunicación de banda ancha
Algoritmos
Computadores
Investigaciones
dc.subject.proposal.spa.fl_str_mv Técnica de clustering
Infraestructura de red
Ancho de banda Traceband
Software libre
description Este proyecto está enmarcado dentro de la línea de investigación en Telemática del grupo de investigación en tecnologías de la información de la UNAB se planteo como objetivo implementar en lenguaje C un algoritmo de clustering en el estimador de ancho de banda Traceband y evaluar impacto del algoritmo en cuanto a la exactitud en la estimación comparada con el programa original, en un escenario controlado que emule el comportamiento de una red en la internet. Para lograr esto, primero se aborda el estudio de mecanismos de clustering y así determinar el que más se ajuste a la problemática de estimación de ancho de banda disponible, después se estudiará el código de Traceband, tanto en el Sender como el Receiver, para determinar el punto en el cual de tiene que aplicar la técnica de clustering seleccionada. Después de tener definido lo anterior, se implementará el código de clustering en lenguaje C y probar la estimación sobre un testbed de evaluación; y así observar la efectividad del algoritmo implementado haciendo pruebas con diferente tipo y cantidad de tráfico cruzado. Para las pruebas, se crea una infraestructura de red que permite evaluar estimadores de ancho de banda disponibles simulando el comportamiento del internet (Testbed). En dicha infraestructura, se evalúa, el Traceband con y sin el K-means, utilizando Mgen para la generación de tráfico. El estimar el ancho de banda disponible es un problema estudiando por investigadores a nivel mundial dada la necesidad de contar con esta información para mejorar la operación de varias aplicaciones de red tales como el cumplimiento de los acuerdos de nivel de servicio, gestión de redes, ingeniería de tráfico y en tiempo real de los recursos de aprovisionamiento, control de flujo y congestión, la detección rápida de fallas, ataques de red y control de admisión [3]. La implementación del K-means en el Traceband, permite determinar, de que manera la agrupación de los datos de la estimación, puede ayudar a mejorar la exactitud de la estimación del ancho de banda disponible en una infraestructura de red. Adicionando los beneficios que provee, el poder conocer y administrar estos factores críticos, que son relevantes en el rendimiento de la red y los servicios que ésta brinda. Actualmente dentro de la bibliografía revisada, no se encuentra registro de la implementación de una técnica de clustering, dentro de una herramienta de estimación de ancho de banda disponible, como Traceband. Esto contrasta con la gran cantidad de trabajos y contribuciones realizados, en la implementación y uso de las técnicas de clustering en varias áreas de la ciencia; siendo muy efectivas a la hora del análisis de los resultados
publishDate 2011
dc.date.issued.none.fl_str_mv 2011
dc.date.accessioned.none.fl_str_mv 2020-06-26T21:34:54Z
dc.date.available.none.fl_str_mv 2020-06-26T21:34:54Z
dc.type.driver.none.fl_str_mv info:eu-repo/semantics/masterThesis
dc.type.local.spa.fl_str_mv Tesis
dc.type.redcol.none.fl_str_mv http://purl.org/redcol/resource_type/TM
dc.identifier.uri.none.fl_str_mv http://hdl.handle.net/20.500.12749/3467
dc.identifier.instname.spa.fl_str_mv instname:Universidad Autónoma de Bucaramanga - UNAB
dc.identifier.reponame.spa.fl_str_mv reponame:Repositorio Institucional UNAB
url http://hdl.handle.net/20.500.12749/3467
identifier_str_mv instname:Universidad Autónoma de Bucaramanga - UNAB
reponame:Repositorio Institucional UNAB
dc.language.iso.spa.fl_str_mv spa
language spa
dc.relation.references.spa.fl_str_mv Salcedo Morillo, Dixon David, Guerrero Santander, Cesar Darío (2011). Implementación y evaluación de un algoritmo de clustering en un estimador de ancho de banda disponible. Bucaramanga (Colombia) : Universidad Autónoma de Bucaramanga UNAB, Universitat Oberta de Catalunya UOC
A.K. Jain, M.N. Murty, P.J. Flynn. “Data Clustering: A Review”, Sept, 1999. [En línea]. Disponible: en: http://www.docstoc.com/docs/19887391/Data-Clustering-A-Review.
Bottou, L., Bengio, Y. Convergence Properties of the K-means Algorithms. Advances in Neural Information Processing”. Systems. MTI Press, 1995.
C. Blake, D. Katabi, S. Katti, “Cross-Traffic: Noise or Data?” Computer Science and Artificial Intelligence Laboratory@MIT, No registra. [En línea]. Disponible: http://nms.lcs.mit.edu/~dina/pub/multiQ.pdf. [Consultado: 10 de mayo de 2010].
C. Guerrero, "Traceband: Available Bandidth Estimation based on a Hidden Markov Model", Ph.D. dissertation, Murdoch University, Murdoch, WA, Australia, 1999.tesis de la University of South Florida., FL, EEUU, 2009.
Carrasquilla Marín, Ulloque Rodríguez, Guerrero Cesar, “Evaluación de técnicas de medición de ancho de Banda disponible “abet’s” http://www.colombiaaprende.edu.co/html/mediateca/1607/articles-109353_archivo.pdf#page=86
Cesar Guerrero, Miguel A Labrador, "On the Applicability of Available Bandwidth Estimation Techniques and Tools". En: Estados Unidos Computer Communications, ISSN: 0140-3664 ed: v.33 fasc.1 p.11 - 22, 2010[Consultado: 22 de abril de 2010].
Cesar Guerrero, Miguel A. Labrador, "Traceband: A fast, low overhead and accurate tool for available bandwidth estimation and monitoring". En: Estados Unidos Computer Networks-The International Journal Of Computer And Telecommunications Networking, ISSN: 1389-1286  ed: v.54 fasc.6 p.977 - 990, 2010. [Consultado: 20 de abril de 2010].
Cristina García Cambronero, Irene Gómez Moreno, “Algoritmos de aprendizaje: KNN & KMEANS”. 14/12/2008. [En línea]. Disponible: www.it.uc3m.es/jvillena/irc/practicas/08-09/06.pdf [Consultado: 20 de mayo de 2010].
DUBES, R. C. 1987. How many clusters are best?—an experiment. Pattern Recogn. 20, 6 (Nov. 1, 1987), 645–663.
Duda, R.O., Hart, P.E.: Pattern Classification and Scene Analysis. John Wiley & Sons, New York, NY. 1973.
E. Hernández, “Algoritmo de clustering basado en entropía para descubrir grupos en atributos de tipo mixto”, agosto de 2006. [En línea]. Disponible: http://www.cs.cinvestav.mx/Estudiantes/TesisGraduados/2006/tesisEdnaHernandez.pdf. Consultado: [5 de enero de 2011].
Fayyad,U. M., Piatetsky-Shapiro, G., Smyth P., Uthurusamy, R.: Advances in Knowledge Discovery and Data Mining. AAAI/MIT Press, 1996.
Filtro K-means (K-Medias). [Web en línea]. Disponible en: <http://celtico-celtico.blogspot.com/>.
Fisher, D.: Knowlwdge Acquisition via Incremental Conceptual Clustering. Machine Learning, Vol. 2, No. 2 (1987) 139-172.
Garre, Cuadrado, Sicilia, “Comparación de diferentes algoritmos de clustering en la estimación de coste en el desarrollo de software,” Universidad del País Vasco, 23 Jun 2005. [En línea]. Disponible: http://www.sc.ehu.es/jiwdocoj/remis/docs/GarreAdis05.pdf. [Consultado: 3 de mayo de 2010].
Google imágenes, [Documento en línea]. Disponible en: <http://www.google.com.co/imgres?imgurl=http://bp0.blogger.com/_FZfs7LCzurk /RbWgQZC04NI/AAAAAAAAADA/8v2zl6wbIB4/s400/flowchart.jpg>
Gustavo Mesa, “Cadenas de markov, una sencilla Aplicación”. Mayo de 2007. [En línea]. Disponible: http://www.revistamemorias.com/articulos9/cadenasdemarkov.pdf [Consultado: 23 de junio de 2010].
Hamerly, G., Elkan, C. “Alternatives to the K-means Algorithm that Find Better Clusterings”. Proc. 11th International Conf. On Information and Knowledge Management CIKM’02. ACM. Virginia, USA (2002).
Implementación-de-k-means-en-opencv. [Web en línea]. Disponible en: <reyesalfonso.blogspot.com/.../implementacion-de-k-means-en-opencv.html>.
J. Pérez, M. F. Henriques, R. Pazos, L. Cruz3, G. Reyes, J. Salinas, A. Mexicano “Mejora al algoritmo de agrupamiento K-means mediante un nuevo criterio de convergencia y su aplicación a bases de datos poblacionales de cáncer”. Centro Nacional de Investigación y Desarrollo Tecnológico (CENIDET), México, Secretaría de Saúde do Estado de Pernambuco, Brasil, Instituto Tecnológico de Ciudad Madero, México.
Julián Moreno, “Aprendizaje de máquina”. No registra. [En línea]. Disponible: http://pisis.unalmed.edu.co/cursos/material/3004653/1/Presentacion.ppt [Consultado: 18 de abril de 2010].
Kanungo, T., Mount, D.M., Netanyahu, N.S., Piatko, C.D., Silverman, R., Wu, A.Y.: A “Local Search Approximation Algorithm for k-Means Clustering” Proc. 18th Annual ACM Symposium on Computational Geometry (SoCG’02). Barcelona, Spain (2002) 10-18.
Kanungo, T., Netanyahu, N.S., Wu, A.Y.: “An Efficient Kmeans Clustering Algorithm: Analysis and Implementation. IEEE Transactions on Pattern Analysis and Machine Intelligence”, Vol. 24, No. 7 (2002).
K-means_clustering Disponible en: <http://en.wikipedia.org/wiki/K-means_clustering>
K-Mediods. Disponible en internet: <http://en.wikipedia.org/wiki/K-medoids>
L.R. Rabiner, “A tutorial on hidden markov models and selected applications in speech recognition”, Proceedings of the IEEE 77 (2) (1989) 257–286.
Lakshminarayanan, Padmananbhan, Padhye, “Estimaciones del Ancho de Banda en redes de Banda Ancha”, Instituto de Ingeniería Eléctrica, No registra. [En línea]. Disponible: http://iie.fing.edu.uy/ense/asign/perfredes/trabajos/trabajos_2004/EstimacionBW/EstimacionBW.pdf. [Consultado: 8 de mayo de 2010].
López Yoel, “Evaluación de técnicas de estimación de ancho de banda disponible en una red de computadoras”. Mayo de 2010. [Archivo PDF]. [Consultado: 20 de mayo de 2010]
M. Zorrilla, “Procesamiento Paralelo y Distribuido Aplicado al Almacenamiento y Recuperación de Información Documental”, 2001. [En línea]. Disponible: http://www.tesisenred.net/TESIS_UC/AVAILABLE/TDR-0927110-130601//TesisMZP.pdf. Consultado: [3 de enero de 2011].
MacQueen, J.: Some Methods for Classification and Analysis of Multivariate Observations. Proc. 5th Berkeley Symp. Math. Statistics and Probability, 1:281-297, 1967.
Martínez Francisco., Quetglás Gregorio. “Introducción a la programación estructurada en C.” Maite Simon, 2003. [E-book] Disponible en: http://books.google.es/
Mehmed, K.: Data Mining: Concepts, Models, Methods, and Algorithms. John Wiley & Sons. 2003.
MGen. [Web en línea]. Disponible en: <http://celtico-celtico.blogspot.com/>.
O. Sánchez, Algunos métodos para medir distancias a los centroides, [En línea]. Disponible: http://omarsanchez.net/Documents/distancias_totales.pdf [Consultado: 22 de diciembre de 2010].
O. Sánchez. “Modelos, Control y sistema de visión”, [Web en línea]. Disponible en: <http://omarsanchez.net/kmeans.aspx>.
Paola Bermolen, “Ancho de Banda Efectivo para Flujos Markovianos” http://www.fing.edu.uy/iie/investigacion/grupos/artes/publicaciones/Paola.pdf
Pelleg, D., Moore, A.: X-means: “Extending K-means with Efficient Estimation of the Number of Clusters”. Proc. 17th International Conf. on Machine Learning (2000).
Peña, J.M., Lozano, J.A., Larrañaga, P. “An Empirical Comparison of Four Initialization Methods for the K-Means Algorithm”. Dept. of Computer Science and Artificial Intelligence, University of the Basque, San Sebastian, España.
R. Prasad, C. Dovrolis, M. Murray, K. Claffy, Bandwidth estimation: metrics, measurement techniques, and tools, IEEE Network 17 (6) (2003) 27–35. [Consultado: 10 de mayo de 2010].
Sanchez, “Algoritmos de agrupamiento”. No registra. [En línea]. Disponible: http://omarsanchez.net/Documents/Agrupamiento_kmeans.pdf [Consultado: 21 de abril de 2010].
Seetharam Samptur. “Available bandwidth inference based on node-centric clusters”. Abril de 2009. [En línea]. Disponible: http://citeecer.ist.psu.edu [Consultado: 19 de abril de 2010].
Shriram, Murray, Hyun, Brownlee, Broido, Fomenkov, kc claffy “Comparison of Public End-to-End BandwidthEstimation Tools on High-Speed Links. 2005.
SPSS, Inc. Headquarters, Chicago, Illinois. http://www.spss.com/es/
dc.rights.uri.*.fl_str_mv http://creativecommons.org/licenses/by-nc-nd/2.5/co/
dc.rights.local.spa.fl_str_mv Abierto (Texto Completo)
dc.rights.accessrights.spa.fl_str_mv info:eu-repo/semantics/openAccess
http://purl.org/coar/access_right/c_abf2
dc.rights.creativecommons.*.fl_str_mv Atribución-NoComercial-SinDerivadas 2.5 Colombia
rights_invalid_str_mv http://creativecommons.org/licenses/by-nc-nd/2.5/co/
Abierto (Texto Completo)
http://purl.org/coar/access_right/c_abf2
Atribución-NoComercial-SinDerivadas 2.5 Colombia
eu_rights_str_mv openAccess
dc.format.mimetype.spa.fl_str_mv application/pdf
dc.coverage.spa.fl_str_mv Bucaramanga (Colombia)
dc.coverage.campus.spa.fl_str_mv UNAB Campus Bucaramanga
dc.publisher.grantor.spa.fl_str_mv Universidad Autónoma de Bucaramanga UNAB
dc.publisher.faculty.spa.fl_str_mv Facultad Ingeniería
dc.publisher.program.spa.fl_str_mv Maestría en Software Libre
institution Universidad Autónoma de Bucaramanga - UNAB
bitstream.url.fl_str_mv https://repository.unab.edu.co/bitstream/20.500.12749/3467/1/2011_Tesis_Dixon_David_Salcedo_Morillo.pdf
https://repository.unab.edu.co/bitstream/20.500.12749/3467/2/2011_Anexo_Dixon_David_Salcedo_Morillo.zip
https://repository.unab.edu.co/bitstream/20.500.12749/3467/3/2011_Tesis_Dixon_David_Salcedo_Morillo.pdf.jpg
bitstream.checksum.fl_str_mv 60e78fa6b9ba939e7fcde5e9f75207ad
69cc4468bbe49533da1114802e8bf8b9
ee247bb753d40c3b1742b8dde704e3bf
bitstream.checksumAlgorithm.fl_str_mv MD5
MD5
MD5
repository.name.fl_str_mv Repositorio Institucional | Universidad Autónoma de Bucaramanga - UNAB
repository.mail.fl_str_mv repositorio@unab.edu.co
_version_ 1814277945522388992
spelling Guerrero, Cesar D.e21911f3-3ec0-4ac9-b7db-7e26b4a31bccSalcedo Morillo, Dixon David239995ac-8f3b-4cfe-b73b-fc45a3357addGuerrero, Cesar D. [0000809357]Guerrero, Cesar D. [_YgBOOcAAAAJ]Guerrero, Cesar D. [0000-0002-3286-6226]Guerrero, Cesar D. [23094317500]Guerrero, Cesar D. [Cesar-Guerrero-2]Guerrero, Cesar D. [cesar-d-guerrero]Guerrero, Cesar D. [cguerrer]2020-06-26T21:34:54Z2020-06-26T21:34:54Z2011http://hdl.handle.net/20.500.12749/3467instname:Universidad Autónoma de Bucaramanga - UNABreponame:Repositorio Institucional UNABEste proyecto está enmarcado dentro de la línea de investigación en Telemática del grupo de investigación en tecnologías de la información de la UNAB se planteo como objetivo implementar en lenguaje C un algoritmo de clustering en el estimador de ancho de banda Traceband y evaluar impacto del algoritmo en cuanto a la exactitud en la estimación comparada con el programa original, en un escenario controlado que emule el comportamiento de una red en la internet. Para lograr esto, primero se aborda el estudio de mecanismos de clustering y así determinar el que más se ajuste a la problemática de estimación de ancho de banda disponible, después se estudiará el código de Traceband, tanto en el Sender como el Receiver, para determinar el punto en el cual de tiene que aplicar la técnica de clustering seleccionada. Después de tener definido lo anterior, se implementará el código de clustering en lenguaje C y probar la estimación sobre un testbed de evaluación; y así observar la efectividad del algoritmo implementado haciendo pruebas con diferente tipo y cantidad de tráfico cruzado. Para las pruebas, se crea una infraestructura de red que permite evaluar estimadores de ancho de banda disponibles simulando el comportamiento del internet (Testbed). En dicha infraestructura, se evalúa, el Traceband con y sin el K-means, utilizando Mgen para la generación de tráfico. El estimar el ancho de banda disponible es un problema estudiando por investigadores a nivel mundial dada la necesidad de contar con esta información para mejorar la operación de varias aplicaciones de red tales como el cumplimiento de los acuerdos de nivel de servicio, gestión de redes, ingeniería de tráfico y en tiempo real de los recursos de aprovisionamiento, control de flujo y congestión, la detección rápida de fallas, ataques de red y control de admisión [3]. La implementación del K-means en el Traceband, permite determinar, de que manera la agrupación de los datos de la estimación, puede ayudar a mejorar la exactitud de la estimación del ancho de banda disponible en una infraestructura de red. Adicionando los beneficios que provee, el poder conocer y administrar estos factores críticos, que son relevantes en el rendimiento de la red y los servicios que ésta brinda. Actualmente dentro de la bibliografía revisada, no se encuentra registro de la implementación de una técnica de clustering, dentro de una herramienta de estimación de ancho de banda disponible, como Traceband. Esto contrasta con la gran cantidad de trabajos y contribuciones realizados, en la implementación y uso de las técnicas de clustering en varias áreas de la ciencia; siendo muy efectivas a la hora del análisis de los resultadosUniversitat Oberta de Catalunya UOCINTRODUCCIÓN 13 1. CONTEXTO DE LA INVESTIGACIÓN 15 1.1 Tema 15 1.2 Definición del problema 15 1.3 Objetivos 17 2. ESTADO DEL ARTE 18 3. FUNDAMENTOS TEÓRICOS 23 3.1 Ancho de banda, Bandwidth en inglés 23 3.1.1 Definición 23 3.1.2 Ancho de Banda Disponible 23 3.1.3 Ancho de banda disponible de extremo a extremo (end to end) 25 3.2 Técnicas de estimación de ancho de banda disponible 27 3.2.1 Métodos PRM (packet rate method) 27 3.2.2 Métodos PGM (packet gap method) 28 3.3 Herramientas de estimación de ancho de banda Disponible (ABETT’S) 31 3.4 Modelo de las cadenas ocultas de markov aplicadas a las herramientas de estimación de ancho de banda (HMM) 33 3.4.1 Definición 33 3.4.2 Aplicaciones 35 3.5 Algoritmos de clustering y sus aplicaciones 38 3.5.1 Definición 38 3.5.2 Algoritmos de agrupamiento 38 3.5.3 Aplicabilidad 39 3.5.4 APRENDIZAJE DE MÁQUINA. 39 3.5.4.1 Aprendizaje supervisado 40 3.5.4.2 Aprendizaje no supervisado 40 3.5.5 K-means 41 3.5.5.1 Inconvenientes 43 3.5.6 Aplicación real de los algoritmos de clustering en herramientas de estimación de ancho de banda disponible 44 3.6 Testbed 45 3.6.1 Definición 45 4. METODOLOGÍA APLICADA 48 4.1 Clustering 48 4.1.1 Clustering Probabilístico 50 4.1.2 Métodos de los k-vecinos (k-medoids) 52 4.1.3 Algoritmo Basado en Densidad 54 4.1.4 Método de las k-medias (K-means) 55 4.1.4.1 Descripción del algoritmo K-means estándar 56 4.2 Algoritmo a utilizar dentro del estimador 58 4.2.1 Implementación del algoritmo 62 4.2.2 Operatividad del k-means en el Traceband 62 5. IMPLEMENTACIÓN DE LA SOLUCIÓN 66 5.1 Instalación las herramientas 66 5.1.1 MGEN 66 5.1.2 Traceband 68 5.2 Descripción del testbed 70 5.3 Diseño de los experimentos 72 5.4 Métricas utilizadas 73 5.4.1 Tiempo de estimación 73 5.4.2 Overhead 73 5.4.3 Error de estimación 73 5.4.4 Ancho de banda disponible con K-means 73 5.5 Procesamiento de la información 74 6. RESULTADOS 76 7. CONCLUSIONES 87 7.1 Traceband con HMM 87 7.2 Traceband con K-means 88 7.3 Traceband con HMM vs Traceband con K-means 89 8. REFERENCIAS BIBLIOGRÁFICAS 91MaestríaThis project is framed within the Telematics research line of the information technology research group of the UNAB, the objective of which was to implement in C language a clustering algorithm in the Traceband bandwidth estimator and evaluate the impact of the algorithm on regarding the accuracy of the estimate compared to the original program, in a controlled scenario that emulates the behavior of a network on the internet. To achieve this, first the study of clustering mechanisms is approached and thus determine the one that best suits the problem of estimating the available bandwidth, then the Traceband code will be studied, both in the Sender and the Receiver, to determine the point at which the selected clustering technique has to be applied. After having defined the above, the clustering code will be implemented in C language and the estimation will be tested on an evaluation testbed; and thus observe the effectiveness of the implemented algorithm by testing with different types and amounts of cross traffic. For the tests, a network infrastructure is created that allows evaluating available bandwidth estimators by simulating the behavior of the internet (Testbed). In this infrastructure, the Traceband with and without the K-means is evaluated, using Mgen for the generation of traffic. Estimating the available bandwidth is a problem studied by researchers worldwide given the need to have this information to improve the operation of various network applications such as compliance with service level agreements, network management, engineering real-time traffic and resource provisioning, flow control and congestion, rapid fault detection, network attacks and admission control [3]. The implementation of K-means in the Traceband, allows to determine, in which way the grouping of the estimation data, can help to improve the accuracy of the estimation of the available bandwidth in a network infrastructure. Adding the benefits it provides, being able to know and manage these critical factors, which are relevant to the performance of the network and the services it provides. Actualmente dentro de la bibliografía revisada, no se encuentra registro de la implementación de una técnica de clustering, dentro de una herramienta de estimación de ancho de banda disponible, como Traceband. Esto contrasta con la gran cantidad de trabajos y contribuciones realizados, en la implementación y uso de las técnicas de clustering en varias áreas de la ciencia; siendo muy efectivas a la hora del análisis de los resultadosModalidad Presencialapplication/pdfspahttp://creativecommons.org/licenses/by-nc-nd/2.5/co/Abierto (Texto Completo)info:eu-repo/semantics/openAccesshttp://purl.org/coar/access_right/c_abf2Atribución-NoComercial-SinDerivadas 2.5 ColombiaImplementación y evaluación de un algoritmo de clustering en un estimador de ancho de banda disponibleImplementation and evaluation of a clustering algorithm in an available bandwidth estimatorMagíster en Software LibreBucaramanga (Colombia)UNAB Campus BucaramangaUniversidad Autónoma de Bucaramanga UNABFacultad IngenieríaMaestría en Software Libreinfo:eu-repo/semantics/masterThesisTesishttp://purl.org/redcol/resource_type/TMClustering techniqueNetwork infrastructureTraceband bandwidthFree softwareSystems engineerBroadband communication systemsAlgorithmsComputersResearchIngeniería de sistemasSistemas de comunicación de banda anchaAlgoritmosComputadoresInvestigacionesTécnica de clusteringInfraestructura de redAncho de banda TracebandSoftware libreSalcedo Morillo, Dixon David, Guerrero Santander, Cesar Darío (2011). Implementación y evaluación de un algoritmo de clustering en un estimador de ancho de banda disponible. Bucaramanga (Colombia) : Universidad Autónoma de Bucaramanga UNAB, Universitat Oberta de Catalunya UOCA.K. Jain, M.N. Murty, P.J. Flynn. “Data Clustering: A Review”, Sept, 1999. [En línea]. Disponible: en: http://www.docstoc.com/docs/19887391/Data-Clustering-A-Review.Bottou, L., Bengio, Y. Convergence Properties of the K-means Algorithms. Advances in Neural Information Processing”. Systems. MTI Press, 1995.C. Blake, D. Katabi, S. Katti, “Cross-Traffic: Noise or Data?” Computer Science and Artificial Intelligence Laboratory@MIT, No registra. [En línea]. Disponible: http://nms.lcs.mit.edu/~dina/pub/multiQ.pdf. [Consultado: 10 de mayo de 2010].C. Guerrero, "Traceband: Available Bandidth Estimation based on a Hidden Markov Model", Ph.D. dissertation, Murdoch University, Murdoch, WA, Australia, 1999.tesis de la University of South Florida., FL, EEUU, 2009.Carrasquilla Marín, Ulloque Rodríguez, Guerrero Cesar, “Evaluación de técnicas de medición de ancho de Banda disponible “abet’s” http://www.colombiaaprende.edu.co/html/mediateca/1607/articles-109353_archivo.pdf#page=86Cesar Guerrero, Miguel A Labrador, "On the Applicability of Available Bandwidth Estimation Techniques and Tools". En: Estados Unidos Computer Communications, ISSN: 0140-3664 ed: v.33 fasc.1 p.11 - 22, 2010[Consultado: 22 de abril de 2010].Cesar Guerrero, Miguel A. Labrador, "Traceband: A fast, low overhead and accurate tool for available bandwidth estimation and monitoring". En: Estados Unidos Computer Networks-The International Journal Of Computer And Telecommunications Networking, ISSN: 1389-1286  ed: v.54 fasc.6 p.977 - 990, 2010. [Consultado: 20 de abril de 2010].Cristina García Cambronero, Irene Gómez Moreno, “Algoritmos de aprendizaje: KNN & KMEANS”. 14/12/2008. [En línea]. Disponible: www.it.uc3m.es/jvillena/irc/practicas/08-09/06.pdf [Consultado: 20 de mayo de 2010].DUBES, R. C. 1987. How many clusters are best?—an experiment. Pattern Recogn. 20, 6 (Nov. 1, 1987), 645–663.Duda, R.O., Hart, P.E.: Pattern Classification and Scene Analysis. John Wiley & Sons, New York, NY. 1973.E. Hernández, “Algoritmo de clustering basado en entropía para descubrir grupos en atributos de tipo mixto”, agosto de 2006. [En línea]. Disponible: http://www.cs.cinvestav.mx/Estudiantes/TesisGraduados/2006/tesisEdnaHernandez.pdf. Consultado: [5 de enero de 2011].Fayyad,U. M., Piatetsky-Shapiro, G., Smyth P., Uthurusamy, R.: Advances in Knowledge Discovery and Data Mining. AAAI/MIT Press, 1996.Filtro K-means (K-Medias). [Web en línea]. Disponible en: <http://celtico-celtico.blogspot.com/>.Fisher, D.: Knowlwdge Acquisition via Incremental Conceptual Clustering. Machine Learning, Vol. 2, No. 2 (1987) 139-172.Garre, Cuadrado, Sicilia, “Comparación de diferentes algoritmos de clustering en la estimación de coste en el desarrollo de software,” Universidad del País Vasco, 23 Jun 2005. [En línea]. Disponible: http://www.sc.ehu.es/jiwdocoj/remis/docs/GarreAdis05.pdf. [Consultado: 3 de mayo de 2010].Google imágenes, [Documento en línea]. Disponible en: <http://www.google.com.co/imgres?imgurl=http://bp0.blogger.com/_FZfs7LCzurk /RbWgQZC04NI/AAAAAAAAADA/8v2zl6wbIB4/s400/flowchart.jpg>Gustavo Mesa, “Cadenas de markov, una sencilla Aplicación”. Mayo de 2007. [En línea]. Disponible: http://www.revistamemorias.com/articulos9/cadenasdemarkov.pdf [Consultado: 23 de junio de 2010].Hamerly, G., Elkan, C. “Alternatives to the K-means Algorithm that Find Better Clusterings”. Proc. 11th International Conf. On Information and Knowledge Management CIKM’02. ACM. Virginia, USA (2002).Implementación-de-k-means-en-opencv. [Web en línea]. Disponible en: <reyesalfonso.blogspot.com/.../implementacion-de-k-means-en-opencv.html>.J. Pérez, M. F. Henriques, R. Pazos, L. Cruz3, G. Reyes, J. Salinas, A. Mexicano “Mejora al algoritmo de agrupamiento K-means mediante un nuevo criterio de convergencia y su aplicación a bases de datos poblacionales de cáncer”. Centro Nacional de Investigación y Desarrollo Tecnológico (CENIDET), México, Secretaría de Saúde do Estado de Pernambuco, Brasil, Instituto Tecnológico de Ciudad Madero, México.Julián Moreno, “Aprendizaje de máquina”. No registra. [En línea]. Disponible: http://pisis.unalmed.edu.co/cursos/material/3004653/1/Presentacion.ppt [Consultado: 18 de abril de 2010].Kanungo, T., Mount, D.M., Netanyahu, N.S., Piatko, C.D., Silverman, R., Wu, A.Y.: A “Local Search Approximation Algorithm for k-Means Clustering” Proc. 18th Annual ACM Symposium on Computational Geometry (SoCG’02). Barcelona, Spain (2002) 10-18.Kanungo, T., Netanyahu, N.S., Wu, A.Y.: “An Efficient Kmeans Clustering Algorithm: Analysis and Implementation. IEEE Transactions on Pattern Analysis and Machine Intelligence”, Vol. 24, No. 7 (2002).K-means_clustering Disponible en: <http://en.wikipedia.org/wiki/K-means_clustering>K-Mediods. Disponible en internet: <http://en.wikipedia.org/wiki/K-medoids>L.R. Rabiner, “A tutorial on hidden markov models and selected applications in speech recognition”, Proceedings of the IEEE 77 (2) (1989) 257–286.Lakshminarayanan, Padmananbhan, Padhye, “Estimaciones del Ancho de Banda en redes de Banda Ancha”, Instituto de Ingeniería Eléctrica, No registra. [En línea]. Disponible: http://iie.fing.edu.uy/ense/asign/perfredes/trabajos/trabajos_2004/EstimacionBW/EstimacionBW.pdf. [Consultado: 8 de mayo de 2010].López Yoel, “Evaluación de técnicas de estimación de ancho de banda disponible en una red de computadoras”. Mayo de 2010. [Archivo PDF]. [Consultado: 20 de mayo de 2010]M. Zorrilla, “Procesamiento Paralelo y Distribuido Aplicado al Almacenamiento y Recuperación de Información Documental”, 2001. [En línea]. Disponible: http://www.tesisenred.net/TESIS_UC/AVAILABLE/TDR-0927110-130601//TesisMZP.pdf. Consultado: [3 de enero de 2011].MacQueen, J.: Some Methods for Classification and Analysis of Multivariate Observations. Proc. 5th Berkeley Symp. Math. Statistics and Probability, 1:281-297, 1967.Martínez Francisco., Quetglás Gregorio. “Introducción a la programación estructurada en C.” Maite Simon, 2003. [E-book] Disponible en: http://books.google.es/Mehmed, K.: Data Mining: Concepts, Models, Methods, and Algorithms. John Wiley & Sons. 2003.MGen. [Web en línea]. Disponible en: <http://celtico-celtico.blogspot.com/>.O. Sánchez, Algunos métodos para medir distancias a los centroides, [En línea]. Disponible: http://omarsanchez.net/Documents/distancias_totales.pdf [Consultado: 22 de diciembre de 2010].O. Sánchez. “Modelos, Control y sistema de visión”, [Web en línea]. Disponible en: <http://omarsanchez.net/kmeans.aspx>.Paola Bermolen, “Ancho de Banda Efectivo para Flujos Markovianos” http://www.fing.edu.uy/iie/investigacion/grupos/artes/publicaciones/Paola.pdfPelleg, D., Moore, A.: X-means: “Extending K-means with Efficient Estimation of the Number of Clusters”. Proc. 17th International Conf. on Machine Learning (2000).Peña, J.M., Lozano, J.A., Larrañaga, P. “An Empirical Comparison of Four Initialization Methods for the K-Means Algorithm”. Dept. of Computer Science and Artificial Intelligence, University of the Basque, San Sebastian, España.R. Prasad, C. Dovrolis, M. Murray, K. Claffy, Bandwidth estimation: metrics, measurement techniques, and tools, IEEE Network 17 (6) (2003) 27–35. [Consultado: 10 de mayo de 2010].Sanchez, “Algoritmos de agrupamiento”. No registra. [En línea]. Disponible: http://omarsanchez.net/Documents/Agrupamiento_kmeans.pdf [Consultado: 21 de abril de 2010].Seetharam Samptur. “Available bandwidth inference based on node-centric clusters”. Abril de 2009. [En línea]. Disponible: http://citeecer.ist.psu.edu [Consultado: 19 de abril de 2010].Shriram, Murray, Hyun, Brownlee, Broido, Fomenkov, kc claffy “Comparison of Public End-to-End BandwidthEstimation Tools on High-Speed Links. 2005.SPSS, Inc. Headquarters, Chicago, Illinois. http://www.spss.com/es/ORIGINAL2011_Tesis_Dixon_David_Salcedo_Morillo.pdf2011_Tesis_Dixon_David_Salcedo_Morillo.pdfTesisapplication/pdf1953487https://repository.unab.edu.co/bitstream/20.500.12749/3467/1/2011_Tesis_Dixon_David_Salcedo_Morillo.pdf60e78fa6b9ba939e7fcde5e9f75207adMD51open access2011_Anexo_Dixon_David_Salcedo_Morillo.zip2011_Anexo_Dixon_David_Salcedo_Morillo.zipAnexoapplication/octet-stream3809777https://repository.unab.edu.co/bitstream/20.500.12749/3467/2/2011_Anexo_Dixon_David_Salcedo_Morillo.zip69cc4468bbe49533da1114802e8bf8b9MD52open accessTHUMBNAIL2011_Tesis_Dixon_David_Salcedo_Morillo.pdf.jpg2011_Tesis_Dixon_David_Salcedo_Morillo.pdf.jpgIM Thumbnailimage/jpeg5179https://repository.unab.edu.co/bitstream/20.500.12749/3467/3/2011_Tesis_Dixon_David_Salcedo_Morillo.pdf.jpgee247bb753d40c3b1742b8dde704e3bfMD53open access20.500.12749/3467oai:repository.unab.edu.co:20.500.12749/34672024-10-16 14:52:36.792open accessRepositorio Institucional | Universidad Autónoma de Bucaramanga - UNABrepositorio@unab.edu.co