PDF de programación - 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 arte

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

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

•
•

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 enlaces 1, 2 y 3, a partir de las mediciones de tiempos de las rutas entre A, B y C. Llamando L1, L2 
y L3 a las demoras en los enlaces y AB, AC y BC a las demoras en las rutas, se puede plantear:

AC=L1L3
BC=L2L3

{AB=L1L2
0 1 1⋅ L1
1 1 0

1 0 1

L3= AB
BC

AC

L2

Empleando notación matricial:

(1.3.1)
(1.3.2)
(1.3.3)

De esa forma se pueden apreciar el vector L de las incógnitas (los valores individuales de los 

enlaces), el vector M de los datos (las mediciones agregadas de las rutas) y una matriz R de ruteo:

R⋅L=M
La matriz de ruteo indica qué enlaces están incluidos en cada ruta.

(1.3.4)

3

Capítulo 1 – Introducción

En este ejemplo, hay 3 incógnitas y 3 ecuaciones independientes, con lo cual el sistema resulta 

compatible determinado y las incógnitas se pueden calcular.

Pero en el caso general, R tiene rango deficiente, lo cual es equivalente a decir que hay menos 
ecuaciones independientes que incógnitas. En ese caso el sistema es indeterminado, y se hace 
necesario adoptar criterios para llegar a una solución.

La deficiencia del rango es causada por diversos motivos. A continuación se darán algunos 

ejemplos.

Falta de mediciones

El ejemplo más simple se da cuando no se tienen todas las mediciones posibles. En un grafo 
mediciones posibles. Si no se contara con 

no dirigido, como el de la figura 1.2.1, hay n⋅n−1
todas ellas, la matriz podría resultar deficiente.

2

Por ejemplo, si no se supiera la demora BC, la matriz quedaría:

R=1 1 0
1 0 1

En este caso, R tiene 3 columnas y rango 2, presentando una deficiencia de 1.

Enlaces que siempre aparecen juntos

En la figura 1.3.1 se puede apreciar un ejemplo en el cual hay un par de enlaces (1 y 4) que 
siempre aparecen juntos. Es decir, para cada fila de R, el valor de las columnas 1 y 4 es siempre el 
mismo. En otras palabras: o aparecen los dos, o no aparece ninguno de los dos. Formalmente:

r i1=r i4 ∀ i

4

Capítulo 1 – Introducción

Figura 1.3.1. Los enlaces 1 y 4 siempre aparecen juntos.

El sistema queda:

AC

L2
L3

1 0 1 1

0 1 1 0⋅L1
L4= AB
BC
1 1 0 1
= AB
0 1 1⋅ L1L4
1 1 0
BC

1 0 1

L2
L3

AC

En este caso, R tiene 4 columnas y rango 3, presentando una deficiencia de 1.

Las incógnitas L1 y L4 no se pueden calcular por separado, pero sí se puede calcular su suma:

Los enlaces 1 y 4 se pueden reemplazar por su concatenación, a la que llamaremos 5. El 

enlace 5 es lo que se denomina un enlace virtual, y se ilustra en la figura 1.3.2. El sistema queda:

0 1 1⋅ L5
1 1 0

L3= AB
BC

1 0 1

AC

L2

Ahora la matriz de ruteo tiene 3 columnas y rango 3, con lo cual no presenta deficiencia.

5

Capítulo 1 – Introducción

Los enlaces virtuales no se utilizan solamente cuando hay enlaces que siempre aparecen 
juntos. Ese es solamente un caso particular de un problema más general: la identificabilidad. Los 
enlaces virtuales se utilizan cuando hay enlaces no calculables individualmente (o sea, al margen de 
todos los demás enlaces de la red). A los enlaces no calculables también se los denomina  no 
identificables. En otras palabras, un enlace es identificable si y solo si su correspondiente incógnita se 
puede despejar, es decir, se puede escribir en función de los datos.

Figura 1.3.2. Un enlace virtual.

Grafos dirigidos

Los ejemplos vistos hasta ahora corresponden a grafos no dirigidos. Eso es equivalente a decir 
que los enlaces son considerados simétricos. Pero si los enlaces tuvieran diferentes propiedades en 
cada uno de sus sentidos, es necesario modelarlos como asimétricos. Es decir, por cada enlace de los 
que se vieron hasta ahora, hay 2: el de ida y el de vuelta. En la figura 1.3.3. se puede apreciar el 
ejemplo original modelado como un grafo dirigido.

6

Capítulo 1 – Introducción

Figura 1.3.3. Un grafo dirigido.

El sistema queda:

L6= AB
0 0 0 1 1 0⋅L1
1 0 0 1 0 0
CB

0 1 1 0 0 0
1 0 0 0 0 1
0 1 0 0 1 0
0 0 1 0 0 1

L2
L3
L4
L5

BA
AC
CA
BC

En este caso, R tiene 6 columnas y rango 5, presentando una deficiencia de 1.

En   los   grafos   dirigidos,   es   un   problema   bastante   común   que   un   determinado  enlace   no   sea 
identificable. Puntualmente en este caso ninguno de los enlaces es calculable, y los enlaces virtuales 
quedan como en la figura 1.3.4.

7

Capítulo 1 – In