Tomografia 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.1. Conceptos básicos

1

1.2. Motivación

2

1.3. El modelo matemático básico

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

554.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ÓNEl á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 intrusionesLas 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 ...