Estudio de la evolución de la topología de
Internet a través de tablas BGP
David Domingo Alegre
Universidad Politécnica de Catalunya
4 de Febrero de 2004
Introducción

Internet crece en varias dimensiones




Servicios ofrecidos
Número de usuarios
Medios de acceso
Se soporta sobre una compleja infraestructura de
interconexión de redes, que tiene que crecer con el
uso de Internet.

El proyecto estudia esta infraestructura de Internet
desde el punto de vista de su evolución temporal.
2
Índice

Objetivos

Background

Estudio




Evolución de las métricas básicas
Evolución de la repartición geográfica
Evolución de las zonas de Internet
Conclusiones y trabajos futuros
3
Índice

Objetivos

Background

Estudio




Evolución de las métricas básicas
Evolución de la repartición geográfica
Evolución de las zonas de Internet
Conclusiones y trabajos futuros
4
Objetivos

Extraer datos de una tabla BGP para construir la
topología de Internet

Repetir el proceso para tablas de diferentes
instantes en el tiempo

Con los datos de la topología, estudiar:




Evolución de las métricas básicas
Evolución de la repartición geográfica
Evolución de las zonas de Internet
Obtener resultados globales de los estudios
5
Índice

Objetivos

Background

Estudio




Evolución de las métricas básicas
Evolución de la repartición geográfica
Evolución de las zonas de Internet
Conclusiones y trabajos futuros
6
Sistemas Autónomos

El Sistema Autónomo es un conjunto de redes y
dispositivos bajo una administración común.
Suelen ser ISP (Internet Service Providers)

Poseen un bloque de direcciones IP que publican
al resto de Sistemas Autónomos para que puedan
llegar a ellas.

Cada Sistema Autónomo esta identificado por un
número de 16 bits.
7
Sistemas Autónomos e Internet
AS 701
AS 65
AS 7
AS 819
AS 120

La agregación de Sistemas Autónomos forma Internet
8
Tipos de relaciones entre Sistemas

Proveedor a Cliente (P2C)
Cliente
AS 7
Proveedor
AS 120

Cliente a Proveedor (C2P)
Proveedor
AS 7
Cliente
AS 120
9
Tipos de relaciones entre Sistemas

Peering (PEER)
Peer
AS 7
Peer
AS 120

Sibling (SIB)
Sibling
AS 7
Sibling
AS 120
10
BGP (Border Gateway Protocol)

BGP es el protocolo de comunicación entre
Sistemas Autónomos
BGP
AS 120

AS 7
BGP establece una conexión TCP y a
continuación empieza a intercambiar rutas a
través de mensajes BGP.
11
Tablas BGP

Las rutas entre Sistemas Autónomos se guardan en
tablas BGP.

Network
NextHop
*> 1.0.0.0
*> 2.0.0.0
* 3.0.0.0
*
*
*
…
64.50.230.1
64.50.230.1
216.140.2.59
64.200.199.4
134.222.85.45
196.7.106.245
…
Metric LocPrf Weight Path
949
20
…
0
0
0
0
0
0
…
4181 65333 i
4181 65333 i
6395 7018 80 i
7911 7018 80 i
209 7018 80 i
2905 701 7018 80
…
Ejemplo (2.0.0.25):
2.0.0.25
AS 105
AS 4181
AS 65333
12
Fuente de tablas BGP

El proyecto RouteViews de la universidad de Oregón
almacena tablas BGP desde el 1997 cada día.
RouteViews
…
…
13
Índice

Objetivos

Background

Estudio




Evolución de las métricas básicas
Evolución de la repartición geográfica
Evolución de las zonas de Internet
Conclusiones y trabajos futuros
14
El grafo de Sistemas Autónomos

Representamos Internet como un grafo:



Los Sistemas Autónomos son los nodos
Las conexiones entre Sistemas Autónomos son las aristas
Una ruta de la tabla BGP indica el camino de aristas
entre dos nodos
Path
4181 65333 i
4181 65333 i
6395 7018 80 i
7911 7018 80 i
209 7018 80 i
2905 701 7018 80
…
AS 7018
AS 209
AS 80
15
De la tabla BGP al grafo

Aplicando scripts se transforma la tabla BGP en la
matriz de adyacencias del grafo de Sistemas
Autónomos.
Path
4181 65333 i
4181 65333 i
6395 7018 80 i
7911 7018 80 i
209 7018 80 i
2905 701 7018 80
…
Matrix
1 2 … 65333 …
1
0 0
2
0 0
…
4181 0 0
…
0
0
1
16
Evolución de los Sistemas Autónomos

Evolución del número de Sistemas Autónomos (nodos):
17
Evolución de las relaciones

Evolución del número de enlaces (aristas):
18
Grado medio de un Sistema Autónomo

Grado de un Sistema Autónomo = número de
relaciones con otros Sistemas Autónomos.

Se divide en grado de salida o grado de entrada
dependiendo del tipo de relación con los otros
Sistemas Autónomos.
Grado de AS 7018 = 2
AS 7018
AS 209
AS 80
Grado de entrada
de AS 7018 = 1
Grado de salida
de AS 7018 = 1
19
Evolución del grado medio

Los Sistemas Autónomos tienen más relaciones:


Los clientes han aumentado su grado por redundancia y balanceo.
Los Sistemas Autónomos están mejor interconectados
20
Índice

Objetivos

Background

Estudio




Evolución de las métricas básicas
Evolución de la repartición geográfica
Evolución de las zonas de Internet
Conclusiones y trabajos futuros
21
Los Internet Routing Registry (IRR)

Los IRRs son organismos registradores de Sistemas
Autónomos.

Cada IRR tiene una base de datos con el número,
nombre y país de cada Sistema Autónomo que ofrece
públicamente.

Se ha usado una base de datos única construida a
partir de la consulta de todos los IRRs.
22
Los Internet Routing Registry (IRR)

Existen 4 IRRs en todo el mundo:
23
Número de Sistemas Autónomos por IRR

Aplicando scripts, calculamos el porcentaje de
Sistemas Autónomos que pertenecen a cada IRR:
30,4%
11,2%
52,5%
3,37%
1,8%
2003-12
24
Número de Sistemas Autónomos por IRR

Evolución temporal del porcentaje de cada IRR:
25
Número de Sistemas Autónomos por Países

Aplicando scripts, calculamos el porcentaje de
Sistemas Autónomos que pertenecen a cada país:
37,6%
49,5%
2,5%
3,12%
3,3%
3,7%
2003-12
26
Número de Sistemas Autónomos por Países

Evolución temporal de la clasificación de países:
27
Índice

Objetivos

Background

Estudio




Evolución de las métricas básicas
Evolución de la repartición geográfica
Evolución de las zonas de Internet
Conclusiones y trabajos futuros
28
Las Zonas de Internet

Internet se puede dividir en tres zonas en base a
la forma en que se interconectan los Sistemas
Autónomos dentro del grafo.

Los Sistemas Autónomos pueden pertenecer a:



Customers: ISPs pequeños que están conectados
únicamente a otro Sistema Autónomo.
Regional ISP: Proveedores medianos que dan servicio a
los Customers.
Core: Pequeña red muy interconectada con los ISP más
importantes y que da servicio a los Regional ISP.
29
Representación de las Zonas de Internet
Regional ISP
Core
Customers
30
Separación del grafo en las 3 zonas

Esta división en 3 zonas es virtual, y para
separarlas, utilizamos la heurística:
“los Sistemas Autónomos con grado de salida = 0
son clientes, es decir, no proveen tráfico a otros
Sistemas Autónomos”.

Ejemplo:
Proveedor
Cliente
AS 7018
AS 209
Grado de entrada
de AS 209 = 1
Grado de salida
de AS 209 = 0
Grado de entrada
de AS 7018 = 0
Grado de salida
de AS 7018 = 1
31
Separación del grafo en las 3 zonas

Aplicamos 2 veces esta heurística sobre el grafo:
1) Separamos los Customers del resto
2) Separamos los Regional ISP del Core

Obtenemos tres grafos con las tres zonas de
Internet que pueden estudiarse cada uno por
separado.
32
Evolución del crecimiento de las zonas

Evolución del porcentaje de Sistemas Autónomos de
cada zona:
33
Evolución del crecimiento de las zonas

Evolución del porcentaje de enlaces de cada zona:
34
Evolución del grado medio de las zonas

El grado de los Regional ISP es respecto a su zona.
35
Índice

Objetivos

Background

Estudio




Evolución de las métricas básicas
Evolución de la repartición geográfica
Evolución de las zonas de Internet
Conclusiones y trabajos futuros
36
Conclusiones

Internet crece a un ritmo constante y lineal. El
número de Sistemas Autónomos y el número de
enlaces no ha parado de crecer en los 5 años.

El Core de Internet cada vez es más pequeño y
tiene más enlaces, por tanto esta más
interconectado.

El coeficiente de clustering en Customers y
Regional ISP se ha mantenido pero en el Core ha
aumentado un 10%
37
Conclusiones

El 55% de Internet se encuentra en Estados
Unidos, el 30% en Europa y el 10% en AsiaPacífico.

Las diferencias entre regiones se van
equilibrando, pero muy lentamente.

En el Core de Internet, la repartición esta mucho
más equilibrada. La mayoría de Customers están
registrados en ARIN.
38
Trabajos futuros

Profundizar en los estudios


Nuevas métricas
Estudiar las causas económicas, sociales y
políticas de esta evolución.


Predicción del futuro



Que requisitos pide cada IRR para ser Sistema
Autónomo?
Como evolucionarán estas métricas en el futuro?
Cuando se acabarán los números para los Sistemas
Autónomos (65535)?
Detallar el estudio del Core
39
Preguntas?
40
Descargar

Diapositiva 1 - David Domingo