Tomografia

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, útil en la administración de la red.

• permite mejorar los protocolos de ruteo.

¿Cuál es entonces la utilidad de la tomografía de la red?

Primero es necesario definir “agregación”. Por ejemplo, la ruta entre dos nodos A y B

atraviesa varios enlaces. El tiempo que tarda un paquete en llegar de A a B es la suma de los tiempos

en cada uno de esos enlaces. Tomar la medición agregada (demora entre A y B) es fácil, pero tomar

una medición individual de los enlaces atravesados es difícil, porque requeriría poder controlar los

puntos unidos por cada enlace.

La respuesta es entonces que todos los parámetros mencionados anteriormente son difíciles o

imposibles de medir en forma directa, pero medianamente fáciles de medir en forma indirecta,

mediante el cruce de información agregada. De aquí deriva la utilidad de la tomografía de la red, que

justamente consiste en el estudio de las propiedades internas (individuales) mediante mediciones

externas (agregadas).

Por ejemplo, la ruta entre A y C posiblemente tendrá una parte en común con la ruta entre A y

B. Es de esperar que los paquetes que salen de A sigan un determinado camino hasta llegar a un punto

en el que se dividen y siguen caminos distintos hacia sus destinos, como se ve en la figura 1.2.1.

2

Capítulo 1 – Introducción

Figura 1.2.1. Un ejemplo simple.

La parte que tienen en común (el enlace 1) aparecerá en dos ecuaciones agregadas

independientes (1.3.1 y 1.3.2). Esto ilustra la posibilidad de cruzar la información agregada.

1.3. El modelo matemático básico

Continuando con el ejemplo simple de la sección anterior, el objetivo es calcular la demora en

los

...