PDF de programación - Compromiso entre Pares e ISPs en el contexto P4P: Optimización en dos niveles

TESIS

presentada el día 9 de Julio de 2010 en la

Universidad de La República, UdelaR

para obtener el título de

MAGISTER EN INGENIERÍA MATEMÁTICA

para

Darío PADULA

Instituto de Investigación : LPE - IMERL

Componentes universitarios :

UNIVERSIDAD DE LA REPÚBLICA

FACULTAD DE INGENIERÍA

Título de la tesis :

Compromiso entre Pares e ISPs en el contexto P4P: Optimización en

dos niveles.

defensa realizada el 29 de Julio de 2010 por el comité de examinadores

RODRÍGUEZ-BOCCA
ROBLEDO AMOZA

Dr. Pablo
Dr. Franco
MSc. Ing. María URQUHART
MSc. Ing. Omar VIERA
Dr. Juan
Dr. Gustavo
Dra. Libertad

KALEMKERIAN
GUERBEROFF
TANSINI

Director de Tesis
Director Académico
Presidente

Agradecimientos

Quiero agradecer a mis tutores Dr. Franco Robledo y Dr. Pablo Rodríguez-Bocca,
por la constante motivación e invaluables aportes durante el proceso de esta tesis. A
los ingenieros Pablo Romero, Andrés Corez y la Lic. Elisa Bertinat no solo por sus
invalorables contribuciones sino también por su gran compañerismo y dedicación.
Al Dr. Eduardo Canale por su desinteresado aporte que resultó de gran utilidad
para la forma de abordar el problema. A los ingenieros Matías Barrios y Claudia
Rostagnol por brindarme la información necesaria para evaluar mis resultados.

Al Ing. Francois Despaux por darme una mano siempre que la necesité.

A la empresa de telecomunicaciones de la República Oriental del Uruguay (AN-
TEL), ya que este trabajo se realizó como parte de la actividad específica “Sistema
eficiente de distribución de video y TV en tiempo real” en el marco del convenio
entre esta y la Facultad de Ingeniería de la Universidad de la República.

Por último quiero agradecer a mi novia, familiares, amigos y compañeros de tra-
bajo por hacerme el aguante y darme ánimo en todo momento.

4

Abstract

El diseño de ruteos para redes peer-to-peer (P2P) tiene muchos desafíos. Los usua-
rios (llamados pares o peers) exigen alta Calidad de Experiencia en las aplica-
ciones que utilizan (compartir archivos, video streaming, etc.) generando un alto
tráfico en la red, el cual por lo general no contempla las limitaciones de la red
de Internet subyacente. Los ISPs (Internet Service Providers) mantienen su ne-
gocio ofreciendo un buen servicio para los usuarios finales tratando de utilizar de
forma eficiente sus recursos (especialmente sus enlaces internacionales que son los
recursos más costosos). Una estrategia reciente que considera conjuntamente los
objetivos de los pares e ISPs es la llamada P 4P [50] (Proactive Provider Parti-
cipation). Esta estrategia coloca el máximo tráfico total en la red, reduciendo al
mismo tiempo el porcentaje de la utilización del enlace internacional más conges-
tionado.

En este trabajo el problema multióbjetivo P4P es resuelto de forma aproximada
mediante un algoritmo FPTAS (Fully Polynomial Time Approximation Scheme)
cuando el objetivo es compartir un sólo contenido en la red. Una metaheurística
basada en GRASP (Greedy Randomized Adaptive Search Procedure) es aplicada
para resolver el problema general, cuando los pares comparten múltiples conteni-
dos. Utilizando instancias generadas aleatoriamente se obtienen muy buenos resul-
tados contrastando las soluciones obtenidas con cotas conocidas.
Finalmente se muestran resultados de emulaciones en una plataforma P2P real lla-
mada GoalBit, contrastando los resultados obtenidos con la metodología P4P ver-
sus una metodología de ruteo aleatoria. Los resultados son alentadores, justificando
el uso de P4P, ya que se logra reducir la utilización de los enlaces internacionales
al mismo tiempo que aumenta la transferencia de flujo neto de los usuarios.

5

6

Índice

1

Introducción

2 Marco Teórico

2.1 Redes P2P .

2.2 El Modelo P4P .

.

.

.

.

.

.
.

.
.

.
2.1.1 BitTorrent .
2.1.2
2.1.3

. . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . .
Streaming de Video P2P . . . . . . . . . . . . . . . . . .
Plataforma GoalBit . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . .
.
Introducción .
. . . . . . . . . . . . . . . . . . . . . . .
Problema Multiobjetivo . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . .
2.3.1
Investigaciones previas de P4P . . . . . . . . . . . . . . .
2.3.2 Resultados previos de implementaciones P4P . . . . . . .
2.3.3 Enfoque Ono .
. . . . . . . . . . . . . . . . . . . . . . .

2.2.1
2.2.2

2.3 Trabajos relacionados .

.

3 Problemas a abordar
.

Introducción .

.

.

.

.

.

3.1
. . . . . . . . . . . . . . . . . . . . . .
3.2 Problema General (PG) . . . . . . . . . . . . . . . . . . . . . . .
3.3 Un contenido, conocimiento completo...
. . . . . . . . . . . . . .
3.3.1 Variante P1: utilización fija de los enlaces (V P 1ρ)
. . . .
3.3.2 Variante P1: Ruteos por caminos de largo uno (V P 1) . . .
3.4 Un contenido, tráfico de fondo parcialmente...
. . . . . . . . . . .
3.5 Un contenido, tráfico de fondo y capacidades parcialmente cono-
cidas (Problema 3 o P3) . . . . . . . . . . . . . . . . . . . . . . .

4 Propiedades y algoritmos para los problemas de un contenido

Instancias y propiedades

. . . . . . . . . . . . . . . . . . . . . .
4.1
4.2 El Problema 3 es polinomial
. . . . . . . . . . . . . . . . . . . .
4.3 Algoritmo de GOTEO para el Problema 2 (P2) . . . . . . . . . . .

7

11

15
15
15
17
17
19
19
22
27
27
28
29

31
31
31
32
33
34
35

36

37
37
40
45

8

ÍNDICE

4.3.1 Waterfilling . . . . . . . . . . . . . . . . . . . . . . . . .
4.3.2 Algoritmo de GOTEO . . . . . . . . . . . . . . . . . . . .
4.4 Algoritmo Goloso para el Problema 1 (P1) . . . . . . . . . . . . .
4.4.1 Greedy y su desempeño en otros problemas . . . . . . . .
4.4.2 Algoritmo goloso simple para P4P . . . . . . . . . . . . .
4.4.3 Contraejemplos de optimalidad para el algoritmo goloso
. . . . . . . . . . . . . . . .
4.4.4 Construcción golosa saturando enlaces
. . . . . . . . . .
4.4.5 Greedy con Waterfilling . . . . . . . . . . . . . . . . . .
4.5 Mejora de la solución . . . . . . . . . . . . . . . . . . . . . . . .
4.5.1 Algoritmo de mejora o completitud . . . . . . . . . . . .

simple . . . . . . . . . . . .

45
46
49
49
50

51
52
55
55
55

5 Algoritmos basado en Ford-Fulkerson

61
62
5.1 Ford-Fulkerson . . . . . . . . . . . . . . . . . . . . . . . . . . .
62
5.1.1 Algoritmo de Ford-Fulkerson . . . . . . . . . . . . . . .
63
5.1.2 Red auxiliar . . . . . . . . . . . . . . . . . . . . . . . . .
68
5.2 Variantes del Problema 1 . . . . . . . . . . . . . . . . . . . . . .
5.2.1 Variante 1: Utilización fija de los enlaces de la red (V P 1ρ)
68
5.2.2 Variante 2: Considerando sólo caminos de largo uno (V P 1) 69
71
72
78
79

. . . . . . . . . . . .
Pasos del algoritmo . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . .
5.4.1 Ruteos que forman ciclos . . . . . . . . . . . . . . . . . .

5.4 Algoritmo para resolver el Problema 1 (P1)

5.3 Algoritmo para resolver el Problema (VP1)

5.3.1

6 Algoritmos para el Problema General (PG)

6.1 Enfoque Metaheurístico . . . . . . . . . . . . . . . . . . . . . . .
6.1.1 Algoritmo Basado en Simplex para Múltiples Contenidos .
6.1.2 Algoritmos Genéticos
. . . . . . . . . . . . . . . . . . .
6.1.3 GRASP . . . . . . . . . . . . . . . . . . . . . . . . . . .

83
84
84
87
88
6.2 GRASP: algoritmo detallado para resolver el Problema General (PG) 91
92
93

Fase 1 (Construcción de una solución factible)
. . . . . .
Fase 2 (Búsqueda Local) . . . . . . . . . . . . . . . . . .

6.2.1
6.2.2

7 Resultados

97

.

.

.

7.2

7.1 Generación de Instancias para el Problema 1 (P1) basadas en datos
97
reales
. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Implementación de distintos algoritmos para el Problema 1 . . . .
99
7.2.1 Generalidades de los algoritmos propuestos e implementados100
7.3 Comparación de resultados . . . . . . . . . . . . . . . . . . . . . 101
7.4 Utilización de la solución en GoalBit . . . . . . . . . . . . . . . . 103

ÍNDICE

9

7.4.1 Emulaciones en GoalBit

. . . . . . . . . . . . . . . . . . 105
7.5 Resultados para el Problema General . . . . . . . . . . . . . . . . 108
7.5.1 Generación de Instancias . . . . . . . . . . . . . . . . . . 110
7.5.2 Cota para el Problema General . . . . . . . . . . . . . . . 111
. . . . . . . . . . . 112
7.5.3 Resultados para el Problema General
. . . . . . . . . . . . . . . . . . . . . . . 119

7.6 Conclusiones

.

.

.

.

.

8 Conclusiones

121
8.1 Conclusiones y contribuciones . . . . . . . . . . . . . . . . . . . 121
8.2 Trabajo a futuro .
. . . . . . . . . . . . . . . . . . . . . . . 124

.

.

.

10

ÍNDICE

Capítulo 1

Introducción

Las redes peer-to-peer (P2P) son redes virtuales que se montan sobre la infraestruc-
tura de Internet. Estas imponen un paradigma que contrasta los clásicos modelos
cliente-servidor, como HTTP y WWW. La esencial distinción se halla en el hecho
que los pares (o nodos pertenecientes a dicha red) también juegan el rol de servi-
dores, aliviando tareas y capacidad de procesamiento de un gran servidor central,
y logrando escalabilidad. Los pares brindan entonces recursos (ancho de banda
y capacidad de procesamiento) a otros pares, básicamente debido a que compar-
ten intereses en común. Los usuarios poseen beneficios evidentes del uso de estas
redes, que permiten aplicaciones de video interactivas, voz, música, tareas distri-
buidas y muchas otras. No obstante, el diseño de estas redes son un gran desafío
desde el punto de vista de la ingeniería de tráfico.
Las ofertas crecientes de banda ancha a nivel mundial facilitan el emergente desa-
rrollo de infraestructuras P2P, donde el ancho de banda de los pares es utilizado
para la distribución de contenidos. Existen muchos ejemplos de sistemas P2P muy
populares para compartir y distribuir archivos como BitTorrent [4], eMule [20], Ka-
ZaA [29], etc, por otro lado existen redes P2P asociadas al streaming (distribución
de audio y video en tiempo real), algunas de estas son PPlive [38], SopCast [45],
CoolStreaming [13]