Tomografía de internet

TOMOGRAFÍA DE INTERNET
TESIS DE GRADO DE INGENIERÍA INFORMÁTICA
SEPTIEMBRE 2007

ALUMNO: ALEJANDRO D. ZYLBERBERG TUTOR: DR. ING. JOSÉ IGNACIO ALVAREZ­HAMELIN

DEPARTAMENTO DE COMPUTACIÓN FACULTAD DE INGENIERÍA UNIVERSIDAD DE BUENOS AIRES

Índice general
1. Introducción 1.1. Conceptos básicos 1.2. Motivación 1.3. El modelo matemático básico 1.4. Problemas inherentes 2. Estado del arte2.1. Tomografía de la red 2.2. Proyectos de mapeo de Internet 2.3. Problemas abiertos 3. Innovaciones 3.1. Determinación de las rutas medibles 3.1.1. Clasificación de nodos 3.1.2. Creación de la matriz de ruteo 3.2. Minimización del sesgo 4. Resultados experimentales 4.1. Simulaciones en diferentes topologías 4.2. Procesamiento de datos reales 4.3. Conclusiones 5. Conclusiones5.1. Contribuciones de esta tesis 5.2. Futuras líneas de investigación iii 1 1 2 3 8 13 13 25 28 31 31 31 48 49 55 56 76 83 85 85 87

Anexo A. Datos experimentales Anexo B. Herramienta de simulación Bibliografía

89 97 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 “end­to­end”, 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: •...