Tomografia
Enviado por danieladd • 14 de Noviembre de 2014 • 1.638 Palabras (7 Páginas) • 314 Visitas
TOMOGRAFÍA DE INTERNET
TESIS DE GRADO DE
INGENIERÍA INFORMÁTICA
SEPTIEMBRE 2007
ALUMNO: ALEJANDRO D. ZYLBERBERG
TUTOR: DR. ING. JOSÉ IGNACIO ALVAREZHAMELIN
DEPARTAMENTO DE COMPUTACIÓN
FACULTAD DE INGENIERÍA
UNIVERSIDAD DE BUENOS AIRES
Índice general
1. Introducción 1
1.1. Conceptos básicos 1
1.2. Motivación 2
1.3. El modelo matemático básico 3
1.4. Problemas inherentes 8
2. Estado del arte 13
2.1. Tomografía de la red 13
2.2. Proyectos de mapeo de Internet 25
2.3. Problemas abiertos 28
3. Innovaciones 31
3.1. Determinación de las rutas medibles 31
3.1.1. Clasificación de nodos 31
3.1.2. Creación de la matriz de ruteo 48
3.2. Minimización del sesgo 49
4. Resultados experimentales 55
4.1. Simulaciones en diferentes topologías 56
4.2. Procesamiento de datos reales 76
4.3. Conclusiones 83
5. Conclusiones 85
5.1. Contribuciones de esta tesis 85
5.2. Futuras líneas de investigación 87
iii
Anexo A. Datos experimentales 89
Anexo B. Herramienta de simulación 97
Bibliografía 99
iv
1. INTRODUCCIÓN
El área de conocimiento en la cual se enmarca la presente tesis se conoce con el nombre de
“Network tomography” o “Tomografía de red”. El término fue utilizado por primera vez por Vardi
[Vardi96] y a lo largo de los 11 años que han transcurrido desde entonces se han publicado gran
cantidad de artículos científicos proponiendo mejoras a la solución original.
En este capítulo se describe la información básica relativa al área de conocimiento. En la
primera sección se explica en qué consiste. En la segunda sección se manifiesta por qué es necesaria.
En la tercera sección se presenta el modelo matemático utilizado habitualmente. Finalmente, en la
cuarta sección se enumeran algunos de los factores que intervienen.
1.1. Conceptos básicos
Comenzaremos por definir a qué llamamos tomografía de una red:
“La tomografía de una red es el estudio de sus
características internas mediante mediciones externas.”
¿Qué significa cada uno de los conceptos que aparecen en esa definición?
• Las características internas son determinadas propiedades de una red, por ejemplo:
• la topología
• la demora en cada enlace
• el porcentaje de paquetes que se pierden en cada enlace
• anomalías e intrusiones
• Las mediciones externas reciben ese nombre porque se toman siempre entre dos nodos de la
red, y nunca se estudia un paquete mientras el mismo está viajando. En inglés se utiliza el
término “endtoend”,
que podría traducirse como “de punta a punta” o “entre puntas”.
• El nombre tomografía, en analogía con el conjunto de técnicas aplicadas en el campo de la
medicina, se utiliza porque se trata de un proceso de medición no invasiva. Esta no invasividad
de las mediciones puede ser entendida de dos maneras:
• Como se menciona más arriba, las mediciones son entre nodos, y no se introduce nada en
1
Capítulo 1 – Introducción
el medio, para, por ejemplo, monitorear directamente un enlace individualmente. Por eso
la llamamos “tomografía”, en vez de, por ejemplo, “endoscopia”.
• Se trata de que el proceso de medición afecte a la red lo menos posible. Esto nos recuerda
en cierta forma al principio de Heisenberg, que básicamente enuncia que no se puede
medir sin interactuar. Cuanto mayor sea la precisión que se busca, mayor es cantidad de
mediciones que deberán ser desplegadas, y entonces los resultados que se obtendrán no
serán los correspondientes a la red original, a la cual se quería evaluar, sino los
correspondientes a la red que se ha modificado a causa del proceso mismo de medición.
1.2 Motivación
La administración de grandes redes requiere información sobre parámetros tales como
topología, conectividad, ruptura de enlaces, comportamiento anómalo, intrusiones, demora de los
enlaces, porcentaje de pérdida de los enlaces, etc.
A modo de ejemplo, podría decirse que obtener las demoras en los enlaces que componen la
red es interesante por motivos como:
• permite trazar un mapa de demoras,
...