Redes de Distribuição de
Conteúdos: Abordagens
Exatas e Heurísticas
Sumário
Motivação
 Problema PPRDR
 Formulação Matemática FD
 Heurística HC
 Resultados Parciais
 Conclusões Parciais
 Trabalhos Futuros

2
Motivação

Alguns conteúdos, como os de multimídia,
necessitam de suporte para que os requisitos
dos clientes sejam satisfeitos

Uso de tecnologias:
•
•
melhoram a qualidade percebida
reduzem os custos operacionais
3
Motivação – Redes de Distribuição de Conteúdos
Clientes
Clientes
Clientes
4
Motivação – Sem RDC
5
Motivação – Sem RDC
6
Motivação – Sem RDC
7
Motivação – Sem RDC
8
Motivação – Sem RDC
9
Motivação - RDC
10
Motivação - RDC
11
Motivação - RDC
12
Motivação - RDC
13
Motivação
14
Motivação - RDC
Reduzir Custos
15
Motivação - RDC
16
Motivação - RDC
17
Problema

Problema de Posicionamento de Réplicas
e Distribuição de Requisições (PPRDR)
Dinâmico e online

Variação do Problema de Posicionamento
de Réplicas (NP-Completo)
18
Problema - Objetivos
Gerenciar o posicionamento das réplicas
 Gerenciar todas as requisições
 Tentar atender a qualidade exigida pelos
clientes
 Minimizar custos ao longo do tempo:
entrega+replicação+atraso

19
Problema - Características

Clientes
•
Têm exigência mínima e capacidade máxima
de banda
• Podem ser atendidos por mais de um servidor

As requisições podem ser atendidas ao
longo do tempo
20
Problema - Características

Servidores são heterogêneos em
capacidade de armazenamento e banda

Informações sobre períodos futuros não
são conhecidas a priori - online
21
Problema Dinâmico - Características

A cada período de tempo podem surgir
novas requisições e novos conteúdos

Conteúdos podem deixar de existir

Condições da rede podem mudar
22
Trabalhos Relacionados - Estático
[Almeida 2004] – PPR. Uso de Árvores
multicast. Modelo matemático, heurísticas
 [Huang 2004] – PPR. Trata a questão da
QoS como alta chance de sucesso.
Abordagem distribuída, dominação de
grafos
 [Bektas 2007] – PPS, PPR. Modelo
matemático, decomposição de Benders,
algoritmo guloso

23
Trabalhos Relacionados - Dinâmico

[Bartolini 2003] –PPR. Processo de
Markov, heurística gulosa

[Zhou 2007] – PR, PPR. Heurísticas e
Simulated Annealing. Considera
informações sobre o futuro
24
Trabalhos Relacionados - Distribuído
[Tenzakthti 2004] – PPR. Heurísticas
centralizada e distribuída
 [Aioffi 2005] – PPR. Modelo matemático,
heurística
 [Wauters 2005] – PPR. Heurísticas
dirigidas por eventos

25
Formulação FD
Variáveis:
 xijt fração do conteúdo solicitado pela requisição
i entregue pelo servidor j no período t
 ykjt 1 se o conteúdo k está replicado no servidor j
no período de t. 0, caso contrário
 bit backlog da requisição i no período t
 wkjlt = 1 se o conteúdo k é copiado pelo servidor
j a partir do servidor l no período t. 0, caso
contrário
26
Formulação
27
Formulação
T=10
C2
S1
28
Formulação
T=10
C2
X2,1,10
S1
29
Formulação
T=10
C2
X2,1,10
S1
30
Formulação
T=10
31
Formulação
T=10
S1
S2
R1
R2
32
Formulação
T=10
S1
Y1,1,10=1
Y2,1,10=0
S2
R1
R2
33
Formulação
T=10
S1
Y1,1,10=1
Y2,1,10=0
S2
R1
Y1,2,10=0
R2
Y2,2,10=1
34
Formulação
35
Formulação
36
Formulação
37
Formulação
38
Formulação
Dit
0
39
Formulação
Dit
40
Formulação
Dit
Xijt
41
Formulação
Dit
Xijt
42
Formulação
Dit
bit
Xijt
43
Formulação
44
Formulação
45
Formulação
46
Formulação
47
Formulação
wkjlt
48
Formulação
T=10
W1,2,1,10=1
S1
S2
R1
49
Formulação FD
Constantes:
 R conjunto de requisições a serem atendidas
 S conjunto de servidores da RDC
 C conjunto de conteúdos a serem replicados
 T conjunto de períodos de tempo
 Lk o tamanho do conteúdo k
 Ok servidor origem do conteúdo k
50
Formulação FD







Bk período em que o conteúdo k é
disponibilizado
Ek período em que o conteúdo k é removido da
RDC
ASj espaço em disco disponível no servidor j
MBj banda máxima do servidor j
Dit demanda da requisição i no período t
BRi banda mínima exigida pela requisição i
BXi banda máxima aceita pela requisição i
51
Formulação FD



g(i) conteúdo exigido pela requisição i
cijt custo de atendimento da requisição i no
servidor j, no período t, calculado pela seguinte
equação
cijt = (RTTorigem(i),j,t + Delayorigem(i),j,t+ ld(i)) BRi
pit penalidade por usar backlog da requisição i
no período t
52
Formulação FD
Min
 c x   p b     L w
ijt
iR jS tT
ijt
it
iR tT
it
k
kC jS
lS { j }
kjlt
(1)
tT
S.a.
L
x  MBj j  S , t  T
g ( i ) ijt
(2)
iR
L
x  bi (t  1)  bit  Dit i  R, t  Bg (i ), Eg (i )
g ( i ) ijt
(3)
jS
53
Formulação FD- Restrições 3
L
x  bi (t  1)  bit  Dit i  R, t  Bg (i ), Eg (i )
g ( i ) ijt
jS
54
Formulação FD- Restrições 3
L
x  bi (t  1)  bit  Dit i  R, t  Bg (i ), Eg (i )
g ( i ) ijt
jS
L
g (i )
xijt  Dit
jS
55
Formulação FD- Restrições 3
L
x  bi (t  1)  bit  Dit i  R, t  Bg (i ), Eg (i )
g ( i ) ijt
jS
L
xijt  Dit
L
xijt  Dit  bi ( t  1)
g (i )
jS
g (i )
jS
56
Formulação FD- Restrições 3
L
x  bi (t  1)  bit  Dit i  R, t  Bg (i ), Eg (i )
g ( i ) ijt
jS
L
xijt  Dit
L
xijt  Dit  bi ( t  1)
g (i )
jS
g (i )
jS
bit   Lg ( i ) xijt  Dit  bi ( t  1)
jS
57
Formulação FD

Lg (i ) xijt  BXi i  R, t  T
(4)
jS
 x
ijt
 1 i  R
(5)
jS tT
yg ( i ) jt  xijt
i  R, j  S , t  T
(6)
58
Formulação
59
Formulação
60
Formulação
61
Formulação FD-Restrições 6
yg ( i ) jt  xijt i  R, j  S , t  T
Y=0 → x=0
Y=1 → x
 [0,1]
62
Formulação FD
 1 k  C, t  Bk , Ek 
(7)
ykjt  0 k  C , j  S , t  Bk , Ek 
(8)
ykOkBk  1 k  C
(9)
y
kjt
jS
63
Formulação FD

ykjBk  0 k  C , j  S j  Ok
ykj (t  1) 
w
kjlt

k  C , j  S , t  T
(10)
(11)
lS
ykjt  wkljt k  C , j  S , l  S , t  T
(12)
64
Formulação FD- Restrições 11
ykj (t  1) 
w
kjlt
k  C , j  S , t  T
i1
lS
ykj (t  1) 
w
kjlt
 ykjt k  C, j  S , t  T
i2
lS { j}
Caso 1(i1): yt+1=0 & yt=0→ somatório em w ≥ 0
Caso 1(i2): yt+1=0 & yt=0→ somatório em w ≥ 0
Caso 2(i1): yt+1=0 & yt=1→ somatório em w ≥ 0
Caso 2(i2): yt+1=0 & yt=1→ somatório em w ≥ 0
65
Formulação FD- Restrições 11
ykj (t  1) 
w
kjlt
k  C , j  S , t  T
i1
lS
ykj (t  1) 
w
kjlt
 ykjt k  C, j  S , t  T
i2
lS { j}
Caso 3(i1): yt+1=1 & yt=0→ somatório em w ≥ 1
Caso 3(i2): yt+1=1 & yt=0→ somatório em w ≥ 1
Caso 4(i1): yt+1=1 & yt=1→ somatório em w ≥ 1
Caso 4(i2): yt+1=1 & yt=1→ somatório em w ≥ 0
66
Formulação FD- Restrições 11
ykj (t  1) 
w
kjlt
k  C , j  S , t  T
i1
lS
ykj (t  1) 
w
kjlt
 ykjt k  C, j  S , t  T
i2
lS { j}
i1 permite que um servidor “envie uma réplica” para ele mesmo
i2 não permite replicação dentro de um mesmo servidor
O uso de i1 implica em uma mudança na função objetivo
explicitando que o envio de um servidor para ele mesmo tem custo
zero.
67
Formulação FD
L y
k kjt
(13)
 ASj j  S , t  T
kC
xijt  0,1 i  R, j  S , t  T
(14)
ykjt  0,1 k  C , j  S , t  T
(15)
bit  0 i  R, t  T
(16)
wkjlt  0,1 j , l  S , k  C , t  T
(17)
68
Heurística HC
Heurística+formulação matemática
 Resolve de maneira exata a associação
requisição-servidor
 Resolve de maneira heurística o
posicionamento das réplicas

69
Heurística HC
Algoritmo HC
1:Para cada período de tempo exceto o último faça
2: Resolver de forma exata a associação requisição-servidor
3: Prevê a demanda para o período seguinte
4: Montar heuristicamente o esquema de replicação para o
próximo período
5:Fim Para
70
Heurística HC - Associação requisição-servidor
Min
 c x   p b
ij
ij
iR jS
S.a.
L
i
i
(18)
iR
x  bi  Di  Bi i  R
g ( i ) ij
(19)
jS
L
x  MBj j  S
(20)
L
x  BXi i  R
(21)
g ( i ) ij
iR
g ( i ) ij
jS
xij  Yg ( i ) j i  R j  S
(22)
xij  0,1 i  R j  S
(23)
bi  0 i  R
(24)
71
Heurística HC - Associação requisição-servidor

A formulação apresentada é contínua

Fácil resolução

Variáveis inteiras são complicadores para
a resolução
72
Heurística HC - Posicionamento de réplicas
Heurística gulosa:

Cada tupla conteúdo/servidor é ordenada
por custo de comunicação

Tenta-se inserir o conteúdo das tuplas de
maior custo nos respectivos servidores
73
Heurística HC - Posicionamento de réplicas
S1
S2
R1
R3
R2
R4
R1=2
R2=2
R3=3
R1=3
R4=4
R4=8
74
Heurística HC - Posicionamento de réplicas
{S1,R4,4} {S2,R1,3} {S1,R2,0} {S2,R3,0}
S1
S2
R1
R3
R2
R4
R1=2
R2=2
R3=3
R1=3
R4=4
R4=8
75
Heurística HC - Posicionamento de réplicas
{S1,R4,4} {S2,R1,3}
S1
S2
R1
R3
R2
R4
R1=2
R2=2
R3=3
R1=3
R4=4
R4=8
76
Heurística HC - Posicionamento de réplicas
{S1,R4,4} {S2,R1,3}
S1
S2
R1
R3
R2
R4
R1=2
R2=2
R3=3
R1=3
R4=4
R4=8
77
Heurística HC - Posicionamento de réplicas
{S1,R4,4} {S2,R1,3}
S1
S2
R1
R3
R1=2
R4
R2
R4
R2=2
R3=3
R1=3
R4=4
R4=8
78
Heurística HC - Posicionamento de réplicas
{S1,R4,4} {S2,R1,3}
R3
S1
S2
R1
R2
R4
R4
R1=2
R2=2
R3=3
R1=3
R4=4
R4=8
79
Heurística HC - Posicionamento de réplicas
{S2,R1,3}
S1
S2
R1
R3
R2
R4
R1=2
R2=2
R3=3
R1=3
R4=4
R4=8
80
Heurística HC - Posicionamento de réplicas
{S2,R1,3}
S1
S2
R1
R3
R2
R4
R1=2
R2=2
R3=3
R1=3
R4=4
R4=8
81
Heurística HC - Posicionamento de réplicas
{S2,R1,3}
S1
S2
R1
R1=2
R3
R4
R3
R2
R2=2
R3=3
R1=3
R4=4
R4=8
82
Heurística HC - Posicionamento de réplicas
S1
S2
R1
R3
R3
R4
R1=2
R2=2
R3=3
R1=3
R4=4
R4=8
83
Resultados – Ambiente computacional

Linguagem C++, g++ 4.3

Quad-Core com 2.83 GHz por core, 8 GB de
RAM, Linux com kernel 2.6

CPLEX 11.2

Instâncias Sintéticas
84
Instâncias
3 classes de Instâncias
 Classe A – Instâncias de Teste
(construídas artesanalmente)
 Classes B e C – Clones. Criadas para
testar capacidade de resolução e impacto
do espaço em disco na qualidade da
solução

85
Instâncias

Topologia:
 Brite
 Waxman
 Sistemas
autônomos
 Topologias de 4 tamanhos: 10,20,30 e 50
86
Instâncias

Servidores:
 Bandas
heterogêneas
 Discos Heterogêneos
 Não mudam ao longo do tempo
87
Instâncias

Conteúdos:
 Tamanhos
diferentes
 Origens Diferentes
 Podem surgir novos conteúdos
 Conteúdos podem ser removidos
88
Instâncias

Requisições:
 Diretamente
proporcional ao número de
servidores
 Diretamente Proporcional ao número de
períodos
 Seguem uma distribuição similar à Zipf
89
Resultados – Avaliação – FD x HC

Número de replicações

Gaps - instâncias com restrição e sem
restrição de espaço

Tempos computacionais
90
Resultados – Número de replicações

20 instâncias

Número de replicações diferente em 5
91
Resultados – Número de replicações
Instância
# Rep. FD
# Rep. HC
Dif. Perc. (%)
1002
49
56
14,285
1005
38
40
5,263
3002
152
160
5,263
3003
148
150
1,351
5003
245
260
6,122
92
Resultados – Gaps

Gaps variam com o tamanho das
instâncias?

A existência de restrição no espaço tem
influência nos Gaps?
93
Resultados – Gaps

Gaps variam com o tamanho das
instâncias?

A existência de restrição no espaço tem
influência nos Gaps?
Testes com 40 instâncias clones:
20 com restrição e 20 sem restrição
94
Resultados – Gaps
10
9
GAP(%)
8
7
6
5
sem restrição
4
com restrição
3
2
1
0
10
20
30
50
Servidores
95
Resultados - Tempos computacionais

Comparar os tempos computacionais

40 instâncias utilizadas
96
Resultados - Tempos computacionais
600
Tempo(s)
500
400
FD1
300
CH
200
100
0
10
20
Servidores
30
50
97
Results – GAP reason

Caused by difference between offline and
online versions of the problem?

Caused by natural difference between
exact and heuristic approaches?
98
PSH Heuristic

Divide the problem into several periods

Solve exactly the problem for each period

Concatenate the solutions for each period
building a solution for the original problem
99
Results – Gaps

PSH results indicates the gaps between
HC and FD are caused mainly by the
difference between approaches

Two possible causes: positioning and
demand estimating
100
HCFK Heuristic

Proceed exactly like HC

Does not estimate future demand

Knows the real demand of next period
101
GHS Heuristic




Replicates contents based only on current
demand (LRU used for discarding replicas)
Requests are handled only by their origin
servers
If the desired content is not in the origin, it is
downloaded and the request is handled
GHS is not competitive for backlogging too
many requests
102
OGHS Heuristic

Requests are handled as in HC and HCFK

Replica positioning is solved as in GHS
103
Results – Gaps
14
450
12
400
350
300
HC
8
PSH
6
HCFK
OGHS
4
Time(s)
GAP(%)
10
HC
250
FD
200
PSH
150
100
2
50
0
0
10
20
30
Servers
50
10
20
30
50
Servers
104
Conclusions
HC solutions are 5.5% from optimal
 PSH and HCFK results indicate that HC
gaps are mainly caused by the heuristic
positioning of contents
 GHS is not proposed for scenarios with
QoS Constraints. Produce poor quality
solutions

105
Conclusions

OGHS outperforms GHS when QoS
constraints are considered

HC outperforms OGHS since it produces
better results in similar time
106
Trabalhos Futuros
Novas Instâncias – Instâncias maiores e
mais difíceis
 Novas Abordagens – Novas heurísticas
usando outras abordagens para os subproblemas

107