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...
- 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 |