Distribuição de Mídia Contínua
Localizaçao e Seleçao
de Servidores e
Roteamento
Jussara M. Almeida
Junho 2005
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
Primeiro Problema : Roteamento
• Protocolos de transmissao minimizam banda do
servidor
– Mas com transmissao na Internet: e o consumo de
banda na rede?
• Como construir a arvore de distribuicao entre
servidor (localizacao fixa) e clientes de forma a
minimizar custo total de transmissao?
– Arvore default da Internet: shortest paths
• E possivel atingir um custo total de banda da
rede proximo do minimo?
– Qual e o minimo?
• E possivel atingir SIMULTANEAMENTE bandas
do servidor e da rede proximos do minimo?
Minima Banda do Servidor
Necessaria (Revisao)
• Se cliente pode escutar numero ilimitado de fluxos,
banda minima do servidor para transmitir um unico
arquivo do inico ao fim e dada por:
• Se cliente pode escutar a 2 fluxos:
Estrategia para Estudar
Banda da Rede
• Primeiro passo: derivar limites inferior e superior
para banda na rede para topologias canonicas
– Shared link com fan-out k
– Daisy chain
– Arvore Balanceada
• Projetar novos algoritmos para construcao da arvore
de distribuicao
– Avaliar com topologias sinteticas variadas
– Considerar limite derivado
• Avaliar impacto do protocolo Bandwidth Skimming
(nao leval em consideracao topologia da rede)
– E possivel reduzir banda na rede se a topologia for levada
em consideracao pelo servidor ao realizar os merges de
fluxos?
Limites para Banda Minima na
Rede: Shared Link com Fan-Out
Limites para Banda Minima na
Rede: Shared Link com Fan-Out
Limites para Banda Minima na
Rede: Shared Link com Fan-Out
Limites para Banda Minima na
Rede: Daisy-Chain
Limites para Banda Minima na
Rede: Daisy-Chain
Limites para Banda Minima na
Rede: Daisy-Chain
Limites para Banda Minima na
Rede: Arvore Balanceada
Limites para Banda Minima na
Rede
• Limites inferior e superior proximos: pode usar
apenas um (inferior) como estimativa de banda min.
Limites para Banda Minima na
Rede
• Limites inferior e superior proximos: pode usar
apenas um (inferior) como estimativa de banda min.
Algoritmos para Construcao da
Arvore de Transmissao
• Shortest Path (SP)
• Greedy Link – All (GL-A): adiciona clientes incrementalmente a
arvore. Cliente mais proximo do servidor adicionado primeiro. A
seguir, insere cliente que pode ser adicionado com menor numero
de links
• Greedy Link – Participants (GL-P): igual a GL-A, mas considera
adicionar links para clientes novos apenas a partir de outros
clientes ou do servidor
• Greedy Cost – All (GC-A): como GL-A, mas ao inves do numero de
links considera o custo total de banda de rede extra ao adicionar
clientes
– Precisa saber a taxa de chegada de cada site
– Estima custo extra usando limites derivados
• Greedy Cost – Participants (GC-P): como GC-A, mas considera
apenas clientes e servidor como ponto de conexao de novos
clientes
Avaliacao
• Redes sinteticas de diferentes tamanhos, numeros de
clientes e taxas de chegadas
• GC-A tem melhor performance, mas SP tem custo
apenas marginalmente maior
• GL-A, GL-P podem ser muito ruins
Banda Servidor X Banda Rede?
• Bandwidth Skimming tem banda do servidor bem
proximo do minimo. E a banda da rede?
• Limite inferior para cliente recebendo 2 fluxos:
• Simulacao com topologias ?
Banda Servidor X Banda Rede?
• Simulacao com topologias ?
Como Reduzir Banda da Rede?
• Network-naïve Bandwidth Skimming: restringe merges
somente entre clientes do mesmo site
Como Reduzir Banda da Rede?
• Network-naïve Bandwidth Skimming: restringe merges
somente entre clientes do mesmo site
Pequeno ganho
Como Reduzir Banda da Rede?
• Network-naïve Bandwidth Skimming: restringe merges
somente entre clientes do mesmo site
Topologia: fan-out com shared link
Network-Naïve e pior
Conclusao: Bandwidth Skimming simples pode levar a banda do servidor
e banda da rede proximos dos valores minimos, SIMULTANEAMENTE
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
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???