Redes de Distribuição de Conteúdos: Abordagens Exatas e Heurísticas

Redes de Distribuição de Conteúdos: Abordagens Exatas e Heurísticas

2

Sumário

Motivação Problema PPRDR Formulação Matemática FD Heurística HC Resultados Parciais Conclusões Parciais Trabalhos Futuros

3

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

4

Motivação – Redes de Distribuição de Conteúdos

Clientes

ClientesClientes

5

Motivação – Sem RDC

6

Motivação – Sem RDC

7

Motivação – Sem RDC

8

Motivação – Sem RDC

9

Motivação – Sem RDC

10

Motivação - RDC

11

Motivação - RDC

12

Motivação - RDC

13

Motivação - RDC

14

Motivação

15

Reduzir Custos

Motivação - RDC

16

Motivação - RDC

17

Motivação - RDC

18

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)

19

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

20

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

21

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

22

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

23

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

24

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

25

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

26

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

27

Formulação

28

FormulaçãoT=10

S1

C2

29

FormulaçãoT=10

S1

C2

X2,1,10

30

FormulaçãoT=10

S1

C2

X2,1,10

31

FormulaçãoT=10

32

FormulaçãoT=10

R1R2

S1 S2

33

FormulaçãoT=10

R1R2

S1 S2

Y1,1,10=1

Y2,1,10=0

34

FormulaçãoT=10

R1R2

S1 S2

Y1,1,10=1

Y2,1,10=0Y1,2,10=0

Y2,2,10=1

35

Formulação

36

Formulação

37

Formulação

38

Formulação

39

Formulação

Dit

0

40

Formulação

Dit

41

Formulação

Xijt

Dit

42

Formulação

Xijt

Dit

43

Formulação

Xijt

bit

Dit

44

Formulação

45

Formulação

46

Formulação

47

Formulação

48

Formulação

wkjlt

49

Formulação

W1,2,1,10=1

R1

S1 S2

T=10

50

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

51

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

52

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

53

Formulação FDMin

Sj

igigitittiijtig EBtRiDbbxL )()()1()( ,,

S.a.

(1)

(3)

(2)

Ri

TtSjMBxL jijtig ,)(

Ri Sj Tt Ri Tt Ck Sj TtjSl

kjltkititijtijt wLbpxc}{

54

Formulação FD- Restrições 3

Sj

igigitittiijtig EBtRiDbbxL )()()1()( ,,

55

Formulação FD- Restrições 3

Sj

itijtig DxL )(

Sj

igigitittiijtig EBtRiDbbxL )()()1()( ,,

56

Formulação FD- Restrições 3

Sj

itijtig DxL )(

Sj

tiitijtig bDxL )1()(

Sj

igigitittiijtig EBtRiDbbxL )()()1()( ,,

57

Formulação FD- Restrições 3

Sj

itijtig DxL )(

Sj

tiitijtig bDxL )1()(

Sj

igigitittiijtig EBtRiDbbxL )()()1()( ,,

Sj

tiitijtigit bDxLb )1()(

58

Formulação FD

TtRiBXxL iijtig

Sj

,)( (4)

(5)

TtSjRixy ijtjtig ,,)( (6)

Sj Tt

Rixijt 1

59

Formulação

60

Formulação

61

Formulação

62

Formulação FD-Restrições 6TtSjRixy ijtjtig ,,)(

Y=0 → x=0

Y=1 → x [0,1]

63

Formulação FD

Sj

kkkjt EBtCky ,,1 (7)

kkkjt EBtSjCky ,,,0 (8)

Cky kkBkO 1 (9)

64

kkjB OjSjCky k ,0 (10)

TtSjCkwySl

kjlttkj

,,)1( (11)

TtSlSjCkwy kljtkjt ,,, (12)

Formulação FD

65

Formulação FD- Restrições 11TtSjCkwy

Sl

kjlttkj

,,)1(

TtSjCkywy kjtkjlttkj

jSl

,,}{

)1(

Caso 1(i1): yt+1=0 & yt=0→ somatório em w ≥ 0

i1

i2

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

66

Formulação FD- Restrições 11TtSjCkwy

Sl

kjlttkj

,,)1(

TtSjCkywy kjtkjlttkj

jSl

,,}{

)1(

Caso 3(i1): yt+1=1 & yt=0→ somatório em w ≥ 1

i1

i2

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

67

Formulação FD- Restrições 11TtSjCkwy

Sl

kjlttkj

,,)1(

TtSjCkywy kjtkjlttkj

jSl

,,}{

)1(

i1 permite que um servidor “envie uma réplica” para ele mesmo

i1

i2

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.

68

Formulação FD(13)

TtSjRixijt ,,1,0 (14)

TtSjCkykjt ,,1,0 (15)

TtRibit ,0 (16)

TtCkSljwkjlt ,,,1,0 (17)

TtSjASyLCk

jkjtk

,

69

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

70

Heurística HC

Algoritmo HC1:Para cada período de tempo exceto o último faça2: Resolver de forma exata a associação requisição-servidor3: Prevê a demanda para o período seguinte4: Montar heuristicamente o esquema de replicação para o próximo período5:Fim Para

71

Heurística HC - Associação requisição-servidor

Ri Sj Ri

iiijij bpxc

Sj

RiBDbxL iiiijig )(

Ri

SjMBxL jijig )(

RiBXxL iijig

Sj

)(

SjRiYx jigij )(

SjRixij 1,0

Ribi 0

Min

S.a.

(18)

(19)

(20)

(21)

(22)

(23)

(24)

72

A formulação apresentada é contínua

Fácil resolução

Variáveis inteiras são complicadores para a resolução

Heurística HC - Associação requisição-servidor

73

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

74

Heurística HC - Posicionamento de réplicas

R1 R2R3 R4

S1 S2

R1=2

R3=3

R4=4

R2=2

R1=3

R4=8

75

Heurística HC - Posicionamento de réplicas

R1 R2R3 R4

S1 S2

R1=2

R3=3

R4=4

R2=2

R1=3

R4=8

{S1,R4,4} {S2,R1,3} {S1,R2,0} {S2,R3,0}

76

Heurística HC - Posicionamento de réplicas

R1 R2R3 R4

S1 S2

R1=2

R3=3

R4=4

R2=2

R1=3

R4=8

{S1,R4,4} {S2,R1,3}

77

Heurística HC - Posicionamento de réplicas

R1 R2R3 R4

S1 S2

R1=2

R3=3

R4=4

R2=2

R1=3

R4=8

{S1,R4,4} {S2,R1,3}

78

Heurística HC - Posicionamento de réplicas

R1

R2R3 R4

S1 S2

R1=2

R3=3

R4=4

R2=2

R1=3

R4=8

{S1,R4,4} {S2,R1,3}

R4

79

Heurística HC - Posicionamento de réplicas

R1

R2

R3

R4

S1 S2

R1=2

R3=3

R4=4

R2=2

R1=3

R4=8

{S1,R4,4} {S2,R1,3}

R4

80

Heurística HC - Posicionamento de réplicas

R1 R2R3 R4

S1 S2

R1=2

R3=3

R4=4

R2=2

R1=3

R4=8

{S2,R1,3}

81

Heurística HC - Posicionamento de réplicas

R1 R2R3 R4

S1 S2

R1=2

R3=3

R4=4

R2=2

R1=3

R4=8

{S2,R1,3}

82

Heurística HC - Posicionamento de réplicas

R1 R2R3 R4

S1 S2

R1=2

R3=3

R4=4

R2=2

R1=3

R4=8

{S2,R1,3}

R3

83

Heurística HC - Posicionamento de réplicas

R1 R3 R4

S1 S2

R1=2

R3=3

R4=4

R2=2

R1=3

R4=8

R3

84

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

85

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

86

Instâncias

Topologia: BriteWaxman Sistemas autônomosTopologias de 4 tamanhos: 10,20,30 e 50

87

Instâncias

Servidores: Bandas heterogêneasDiscos HeterogêneosNão mudam ao longo do tempo

88

Instâncias

Conteúdos: Tamanhos diferentesOrigens DiferentesPodem surgir novos conteúdosConteúdos podem ser removidos

89

Instâncias

Requisições:Diretamente proporcional ao número de

servidoresDiretamente Proporcional ao número de

períodosSeguem uma distribuição similar à Zipf

90

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

91

Resultados – Número de replicações

20 instâncias

Número de replicações diferente em 5

92

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

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?

94

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

95

Resultados – Gaps

0

1

2

3

4

5

6

7

8

9

10

10 20 30 50Servidores

GA

P(%

)

sem restrição

com restrição

96

Resultados - Tempos computacionais

Comparar os tempos computacionais

40 instâncias utilizadas

97

Resultados - Tempos computacionais

0

100

200

300

400

500

600

10 20 30 50Servidores

Tem

po

(s)

FD1

CH

98

Results – GAP reason

Caused by difference between offline and online versions of the problem?

Caused by natural difference between exact and heuristic approaches?

99

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

100

PSH results indicates the gaps between HC and FD are caused mainly by the difference between approaches

Two possible causes: positioning and demand estimating

Results – Gaps

101

HCFK Heuristic

Proceed exactly like HC

Does not estimate future demand

Knows the real demand of next period

102

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

103

OGHS Heuristic

Requests are handled as in HC and HCFK

Replica positioning is solved as in GHS

104

Results – Gaps

0

2

4

6

8

10

12

14

10 20 30 50

Servers

GA

P(%

)

HC

PSH

HCFK

OGHS

0

50

100

150

200

250

300

350

400

450

10 20 30 50

Servers

Tim

e(s) HC

FD

PSH

105

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

106

Conclusions

OGHS outperforms GHS when QoS constraints are considered

HC outperforms OGHS since it produces better results in similar time

107

Trabalhos Futuros

Novas Instâncias – Instâncias maiores e mais difíceis

Novas Abordagens – Novas heurísticas usando outras abordagens para os sub-problemas