Optimizacion IP/MPLS

TESIS
a ser presentada el día 11 de Febrero de 2011, en la

Universidad de La República, UdelaR
para obtener el título de

M AGISTER EN I NGENIERÍA M ATEMÁTICA
para

Ing. François D ESPAUX
Instituto de Investigación : LPE-IMERL
Componentes universitarios :
UNIVERSIDAD DE LA REPÚBLICA, FACULTAD DE INGENIERÍA

Título de la tesis :

Optimización de una Red de Datos IP/MPLS
sobreSDH/DWDM usando Tabú Search.
Caso de estudio: Red de Datos de un Operador de Telefonía Nacional

a realizarse el 11 de Febrero de 2011, por el comité de examinadores
Dr. Ing. Franco
Dr. Gerardo
Dr. Jorge
MSc. Ing. Maria
MSc. Ing. Omar
MSc. Ing. Pedro
Ing. Diego

ROBLEDO
RUBINO
I GLESIAS
U RQUHART
V IERA
P IÑEYRO
VALLE L ISBOA

Director de Tesis
Co-Director de Tesis
Presidente2

Index

Índice general
I

Introducción

11

1. Introducción

13

1..

13

2..

Objetivos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

13

3..

Trabajos Previos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

14

4..

II

Motivación . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . .

Organización del Documento . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

15

Marco Teórico

17

2. Descripción del Problema
1..

19
19

1..1.

Redes Overlay . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

19

1..2.

MPLS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

20

1..3.

Redes de Acceso . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . .

20

1..4.

Redes de Transporte . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

20

1..5.
2..

Introducción . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Red de Datos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

21

El Problema a Abordar . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . .

21

3. Formalización de Entidades del Problema
1..

23

Red de Datos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

23

1..1.

Nodos de Datos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

23

1..2.

Las Aristas de Datos . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

25

34

ÍNDICE GENERAL
2..

Red de Transporte . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

25

2..1.

Nodos de Transporte . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

26

2..2.

Aristas de Transporte . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

26

2..3.

Relación entre Transporte y Datos . . . . . . . . . . . . . . . . . . .. . .

27

2..4.

Atributos del Problema . . . . . . . . . . . . . . . . . . . . . . . . . . . .

27

4. Modelización Algebraica del Problema
1..

31
31

1..1.

Definiciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

31

1..2.

Modelo Matemático . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

33

Modelo de Conexión Acceso-Edge . . . . .. . . . . . . . . . . . . . . . . . . . .

35

2..1.

2..

Modelo Completo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

38

Modelo matemático MORN-Reducido . . . . . . . . . . . . . . . . . . . .

5. Complejidad Computacional

41

1..

41

2..

P y NP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

42

3..NP-Completitud . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

42

4..

Complejidad del Algoritmo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

43

4..1.

Condiciones Para la 2-Arista-Conectividad . . . . . . . . . . . . . . . . .

43

4..2.

III

Introducción . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ....