Distribuição de Mídia Contínua
Localizaçao e Seleçao
de Servidores e
Roteamento
Jussara M. Almeida
Junho 2004
Rede
“Local”
Rede
“Local”
Servidor
Proxy
Rede
“Local”
Servidor
Proxy
Servidor
Proxy
Problema
Servidor
Origem
Rede Remota
1) Quantos servidores e onde?
2) Qual servidor cada cliente vai contactar
3) Qual a rota da resposta?
Objetivo: min custo total de transmissao
Precisa: topologia da rede,
custos relativos de
transmissao na rede e do servidor
Metodologia
• Derivacao de soluçao otima
– Modelo de otimizacao de custo
• Analise de topologias canonicas com 2 ou 3
clientes
– Obtencao de intuicao sobre o problema
• Derivacao de várias heuristicas
• Avaliacao com topologias reais da Internet
– Escolha criteriosa
Topologias de Rede
• Topologias a nivel de roteadores e a nivel de
Autonomous Systems (AS)
– Custo de fluxo multicast ainda em aberto
• Topologia a nivel de roteadores:
–
–
–
–
1000 Traceroutes entre pares de sites
24 Sites: laboratorios, universidades, ISPs
Distribuiçao geografica: 4 continentes
Cada site representa subrede local
• Topologia a nivel de AS
– Mapeamento da topologia de roteadores e tabelas BGP
– Mais realista do que simplesmente usar tabelas BGP,
como em trabalhos anteriores
• Exemplo da Fig. 1
Premissas
• Otimizacao de localizacao e roteamento para
conjuntos de client sites
• Arvore de distribuicao fixa
• Custo de transmissao = custo de rede + de servidor
– Proporcional a banda de rede e banda de servidor
– Banda de rede: soma da banda em cada hop das árvores
de distribuicao
• Hop = AS ou link entre dois roteadores
– Chegada de requisicoes: Poisson (banda logaritmica)
– Cada replica: objeto completo, um unico objeto
• Extensoes Futuras:
– Segmentos : interatividade
– Multiplos objetos
Solucao Otima
• Exemplos (Figs 2 e 3)
• Modelo de Otimizacao de Custo (Fig 4)
– Solucao para varios protocolos
– localizacao e roteamento otimos para numero m de
servidores
– Varia m para determinar solucao otima.
• Em comparacao com modelos anteriores
– Solucao conjunta para roteamento e localizacao
– Modelo para BW Skim e Patching: nao lineares nao
convexas : problema!
– Reformulacao do modelo: complexidade alta!
• Tabelas com bw pre-computadas
• Aproximacao linear
– Restricoes adicionais para reduzir espaco de busca
Experimentos com Modelo de Otimizacao
• Comparar:
– Custo da solucao otima para BW Skimming
– Custo se solucao otima para unicast e usado para
transmissao via BW Skimming
• Instalacao de servidores:
clientes ou pontos de entroncamento
• Custo relativo de banda do servidor e da rede, : ??
– Nossos experimentos:  = 0
• Topologias:
– AS e roteadores
– Diferentes niveis de dispersao dos clientes: importante!
– Distribuicao da carga entre clientes:
homogenea e heterogenea
Experimentos com Modelo de Otimizacao
• Figs 5 e 6
• Conclusoes:
– Solucoes otimas para unicast podem ser
significativamente subotimas para multicast
– Necessidade de heuristicas eficientes: modelo
demora muito pra rodar
– Numero otimo de replicas: tradeoff entre banda
de rede e banda de servidor
• Modelo inclui este tradeoff de maneira mais precisa
que trabalhos anteriores
Analise de Arvores Canonicas
• Arvore de Distribuicao Otima (tmin)
– Custo :
• Soma da banda de cada link; a bada de cada link e logaritmica na taxa
de requisicoes
• Trade-off entre min caminhos entre servidor e clientes & max
compartilhamento nos links
• Arvore de Menor Numero de Links (tfl): max.
compartilhamento, mas alguns caminhos podem ser longos
• Arvore dos Caminhos mais Curtos (tsp): min. caminhos, mas
baixo compartilhamento
Analise de Arvores Canonicas
• Topologia canonica, com 2 sites clientes
S
a
c
b
• Conclusoes:
Arvore de Caminhos mais Curtos
A
servidor
d
Site cliente
B
Custo total de transmissao aumenta, no maximo, em
1
f 1
 100%
d
f 
bc
onde f e a razao entre o comprimento do caminho mais curto
entre os clientes e a soma dos comprimentos dos segmentos
nao compartilhados entre servidor e clientes.
Arvore com Menor Numero de Links: custo ilimitado (teorico)
Localizacao de Servidores: nenhuma regra simples encontrada
Heuristicas para
Localizacao de Servidores
Localizacao do primeiro servidor:
– No em S cuja arvore de caminhos mais curtos
para todos os clientes tem custo minimo
Heuristicas: Localizacao de Servidores
Localizacao do ith servidor (i  1): 2 alternativas
1. Min cost tsp
– Considere cada no servidor em S ainda nao usado
– Cada cliente contacta o servidor mais proximo
– Seleciona o no que, juntamente com as arvores ja criadas, tem o
menor custo total das arvores de caminhos mais curtos
2. Maximum Savings
– Considere cada no servidor ainda nao usado que esta em uma das
i-1 arvores criadas previamente
– Selecione o no que acarreta a maior economia de banda quando
removido
– Se nao houver nenhum no, use min cost tsp
Otimizacao: mover servidor da raiz para algum no interno se
acarretar economia de banda
Heuristicas para Roteamento
Construcao da arvore de distribuicao:
1.
Min-Inc-Cost: [ZhEV02]
– Adiciona, a seguir, o cliente que pode ser conectado a
qualquer uma das arvore com custo incremental
minimo
2.
Ordered MinCost:
– Adiciona clientes em ordem decrescente de carga
– Conecta cliente a arvore com custo incremental
minimo
3.
Shortest Path Routing
bom desempenho para um servidor [ZhEV02]
aumento de custo sobre otimo limitado
Avaliacao das Heuristicas
•
Todas heuristicas produzem solucoes proximas do otimo
para nossas topologias
(Fig. 7)
(heterogeneas, homogeneas, AS, roteadores, diferentes niveis de dispersao)
•
•
•
–
–
–
–
–
–
Localizacao:
min-cost tsp igual ou melhor que maximum savings
min-cost tsp melhor que solucoes tradicionais (unicast)
min-cost tsp produz solucoes ate 16% do otimo (nos exps)
Se min-cost tsp
shortest path = ordered min cost = min-inc-cost
(min-inc-cost mais complexo)
Shortest path routing: custo ate 28% maior que otimo
Maior que no paper da Yanping
Menor que limite analitico:
Caracteristicas dos caminhos na Internet???