Algoritmos para Replicação de Objetos em Redes de
Distribuição de Conteúdo

André Luiz de Oliveira
aldo@dcc.ufmg.br - Luiz Henrique Gomes
lhg@dcc.ufmg.br - Renan Oliveira da Cunha
renan@dcc.ufmg.br -
Departamento de Ciência da Computação
Universidade Federal de Minas Gerais
Belo Horizonte - MG - Brasil

Resumo - A distribuição de conteúdo na Internet tem migrado de uma arquitetura onde os objetos são armazenados em um único servidor para uma arquitetura onde os objetos são replicados em servidores distribuídos geograficamente. Neste caso, os clientes acessam transparentemente a cópia mais próxima do objeto desejado, melhorando o desempenho do sistema. Neste trabalho apresentamos um modelo para o estudo destas redes de distribuição de conteúdo, conhecidas como CDN's (Content Distribution Networks). Utilizando este modelo, avaliamos quatro heurísticas para a replicação de objetos através de simulação. Os resultados dos experimentos mostram o ganho significativo de desempenho do sistema ao utilizarmos qualquer um dos algoritmos. Além disso, os melhores resultados foram obtidos quando todos os servidores trabalham cooperativamente para a replicação dos objetos.

Abstract - Content distribution on the Internet is moving from an architecture where objects are placed on a single, designated server to an architecture where objects are replicated on geographically distributed servers. With this new architecture, clients can transparently access a nearby copy of an object. In this paper we propose a model for studying these Content Distribution Networks (CDNs). Using this model, we avaliate four different heuristics for objects replication. The results of the experiments show the significant improvement of the system performance through the utilisation of any algorithm. Furthermore, the best results were obtained with heuristics that have all the CDN servers cooperating in making the replication decisions.

Introdução

Devido ao grande crescimento do número de usuários da Internet, os sites Web têm recebido um volume cada vez maior de requisições. Esse aumento do número de requisições tem elevado a carga de seus servidores e dos meios de comunicação, impondo aos usuários tempos de respostas cada vez mais elevados. Os fatores acima estão motivando os administradores dos sites Web a procurar por alternativas para minimizar esses problemas.

Nesse contexto, foram desenvolvidas as Redes de Distribuição de Conteúdo (CDN - Content Distribution Network). Uma CDN consiste em uma vasta rede de servidores, espalhados por uma área geográfica e ligados através de uma rede proprietária. O conteúdo dos sites Clientes são replicados pelos servidores, de modo que, ao receber uma requisição, a rede escolhe, utilizando algum mecanismo de despacho de requisições, a melhor réplica para atender àquela solicitação [1].

Os trabalhos relacionados foram analisados na seção 2. Na seção 3, será feita uma descrição e contextualização do problema de replicação de objetos em CDNs. A seção 4 descreve um modelo matemático para o problema que é utilizado na seção 5 para mostrar que o problema tratado é NP-Completo. A seção 6 apresenta uma descrição e os pseudo-códigos das heurísticas que serão avaliadas. Na seção 7, é descrito o modelo de simulação utilizado. Os resultados da simulação são avaliados na seção 8 e, na seção 9, encontram-se as conclusões e os trabalhos futuros.

Trabalhos Relacionados

Em [2] é apresentado uma comparação das quatro heurísticas apresentadas neste trabalho, através de simulação. Porém, foram utilizadas taxas iguais para a popularidade de todos os objetos, idependentemente do AS. Além disso, o tamanho dos objetos foi modelado através de uma distribuição uniforme, o que não representa a realidade deste tipo de ambiente.

No trabalho [3] foi apresentado uma comparação de desempenho entre CDNs, tendo sido utilizado um método empírico para fazer tal comparação. Neste trabalho constatou-se que 98% dos objetos servidos pelas CDNs são imagens, representando 40% do total de bytes servidos pelas CDNs.

Em [4] foram apresentadas diversas técnicas para despacho de requisições entre sites Web. Embora o enfoque do trabalho não seja o despacho de requisições em CDNs, ele descreve todas as técnicas geralmente utilizadas pelas CDNs.

Em [5] está descrita uma arquitetura para redirecionamento de requisições entre CDNs. Também são apresentadas motivações para a interoperação de CDNs, e uma avaliação do desempenho de um sistema para a realização deste redirecionamento.

Descrição do Problema

Entre as tecnologias mais utilizadas para minimizar os problemas de tempo de resposta dos usuários Web estão as Web farms. Uma Web farm consiste em ativar diversos servidores Web, capazes de responder por determinado conteúdo, ligados a um switch, funcionando como um dispatcher para requisições de conteúdo [1].

Um dos problemas das Web farms é que o tempo de resposta, devido ao congestionamento da Internet, não é afetado pelo seu uso. Somente o tempo de resposta do servidor Web propriamente dito é reduzido.

Web caches têm sido utilizados com muito sucesso para reduzir o tempo de resposta devido ao congestionamento da Internet, indiferentemente dos pontos da rede em que se localizam e do número de usuários de um site Web [6].

As CDNs surgem com o objetivo de minimizar as limitações das duas tecnologias citadas acima. Utilizando CDNs, a distância entre os usuários e os sites Web diminui pois, dentro da área geográfica atendida por esta, sempre será possível encontrar um servidor mais próximo do Cliente em termos de latência de rede, do que o servidor original. Além disso, como o atendimento aos usuários será feito por um número muito maior de servidores, a carga do servidor original será reduzida e, consequentemente, o tempo de resposta dos servidores Web.

Atualmente, diversos sites Web são Clientes de CDNs comerciais (ex. Akamai [7], Digital Island [8] etc). O objetivo de uma Rede de Distribuição de Conteúdo comercial não se restringe à redução do tempo de resposta percebidos pelos usuários de seus Clientes, abrangendo também a redução da carga da rede e dos servidores de seus Clientes.

Como CDNs consistem de uma tecnologia relativamente nova no contexto da Internet, existem diversos problemas relacionados à esta tecnologia ainda não resolvidos. Um desses problemas trata-se da escolha do servidor para atender a requisição.

Este problema consiste em descobrir qual é o melhor servidor para atender a uma requisição de um usuário, ou seja, o servidor de despacho de requisições da CDN recebe uma requisição de um usuário e baseado em informações sobre os servidores e o cliente ele determinará qual servidor irá atender àquela requisição [4].

Outro problema é a verificação da atualidade dos objetos armazenados em um servidor da CDN. Os diversos servidores da CDN precisam saber se as cópias que eles detêm dos objetos foram ou não modificadas no servidor original. Portanto, eles necessitam de um mecanismo de comunicação, de modo que cópias desatualizadas sejam reconhecidas e, consequentemente, não sejam fornecidas aos usuários [9].

Mais recentemente, surgiu a necessidade de cooperação entre CDNs, de modo que um Cliente possa ser atendido por diversas CDNs que, em geral, operam em áreas distintas. Sendo assim, surgiu um novo problema para as redes CDNs. Que consiste no problema de escolha do melhor servidor para atender a uma determinada requisição de forma que essa decisão seja tomada em conjunto pelos servidores de mais de uma CDN [5].

O problema estudado neste trabalho consiste da replicação de objetos entre os servidores dos Clientes e os da CDN. Estas réplicas podem ser realizadas de duas formas [9]: cópia prévia - neste caso, faz-se uma cópia dos objetos nos diversos servidores da CDN antes que eles seja requisitados, baseado em um algoritmo qualquer; e cópia dinâmica - neste caso, a cópia é feita na hora em que a requisição é efetuada. O objeto é repassado ao Cliente e armazenado no servidor ao mesmo tempo.

Modelo Matemático do Problema

Para modelagem do problema [2] é considerado uma rede onde os AS's (Autonomous Systems) são os nodos da rede. Não são feitas distinções entre AS's e ISP's (Internet Service Providers). Nós consideramos I AS's na rede. J é o número de objetos passíveis de replicação, sendo o_j um objeto, o seu tamanho é representado por b_j. Os objetos sempre estarão disponíveis no seu AS de origem. O posicionamento dos objetos nos AS's pode ser descrito como uma matriz X, como abaixo:

$\begin{displaymath} x_{ij} = \left \{ \begin{array} {ll} 1 & \mbox{se o objet... ...$AS_{i}$} \ 0 & \mbox{caso contrário} \end{array} \right. \end{displaymath}$

S_i é o espaço, em bytes, disponível para armazenamento de réplicas no AS_i. Os espaço ocupado pelos objetos que estão originalmente no AS_i não estão incluídos em S_i. Podemos escrever a seguinte restrição:

$\sum_{j=1}^{J} b_{j}x_{ij} \leq S_{i} i = 1,2,\ldots,I$

O posicionamento inicial dos objetos é representado por x_o. A taxa agregada de requisições de objetos ao AS_i é representada por $\lambda_{i}$ . Consideramos, também, p_ji a probabilidade de acesso ao objeto j no AS_i.

O objetivo das heurísticas é, encontrar uma matriz de alocação X de modo que tenhamos que percorrer o menor número de hops inter-AS possível para o atendimento das requisições dos usuários, ou seja, para que o atendimento de uma requisição do usuário tenha que passar pelo menor número possível de AS's [2]. O número médio de hops que uma requisição deve atravessar vinda do AS_i é dada por:

$C_{i}(X) = \sum_{j=1}^{J} p_{ji}d_{ij}(X)$ (1)

onde, d_ij(x) é a menor distância para copiar um objeto j para o AS_i considerando a matriz de posicionamento X (considerando que a cópia pode ser feita do AS de origem, ou de uma cópia existente em outro AS). É considerado que o Cliente é sempre redirecionado para o AS mais próximo que tem uma cópia do objeto requisitado:

$C(X)=\frac{1}{\Lambda} \sum_{i=1}^{I} \lambda_{i}C_{i}(X) =\frac{1}{\Lambda} \sum_{i=1}^{I} \sum_{j=1}^{J} \lambda_{i}p_{j=1}d_{ij}$
$=\sum_{i=1}^{I} \sum_{j}^{J} s_{ij}d_{ij}(x)$

onde $s_{ij}=\frac{\lambda_{i}p_{ji}}{\Lambda}$ .

Prova de NP-Completo

Para provar que o problema é NP-completo, faremos uma formulação do problema como um problema de decisão [2] : dado um número de hops T, o problema de decisão pode ser formulado da seguinte forma: existe uma matriz de posicionamento dos objetos X, tal que:

$\sum_{i=1}^{I} \sum_{j=1}^{J} s_{ij}d_{ij}(x) \leq T$

sujeito a $\sum_{j=1}^{J} b_{j}x_{ij} \leq S_{i}$ $i=1,2,\ldots,I$ ?.

A prova de que o problema é NP-Completo será feita em duas etapas [10] [2]:

Provaremos que o problema é NP: dada uma matriz de posicionamento X, podemos verificar em tempo polinomial que este posicionamento resulta em um custo médio menor ou igual a T. Para tanto, basta calcular os valores s_ij e d_ij(x) e utilizar a fórmula acima.

Mostraremos uma redução polinomial do problema da mochila no nosso problema: façamos S₁=S; S_i=0; $i=2,3,\ldots,I$ ; $\lambda_{i}=\lambda$ ; $i=1,2,\ldots,I$ ; p_ji=p; $j=1,2,\ldots,J$ e $i=1,2,\ldots,I$ .Ou seja, nós temos apenas um AS onde replicar os objetos. Todos os AS's têm a mesma taxa de acesso e todos os objetos são igualmente populares.

Como cada objeto j está sempre disponível no AS de origem, o custo de buscar um objeto j para um Cliente do AS_i é d_ij(x₀). Dado que os Clientes sempre vão à cópia mais próxima para atender a uma requisição, colocar cópia dos objetos no único AS disponível deverá sempre reduzir o tempo de acesso a um objeto, e portanto

$d_{ij}(x) \leq d_{ij}(x_{0})$ para todo i e j.

Definamos a utilidade da replicação do objeto j como no AS_i:

$u(j)=\sum_{i=1}^{I} [d_{ij}(x_{0}) - d_{ij}(x)]$

Ou seja, a redução do número de hops que conseguimos se replicarmos o objeto j no AS.

Desta forma, podemos descrever o problema da seguinte forma:

$\sum_{j=1}^{J'}b_{j} \leq S$ e $\sum_{j=1}^{J'}u(j) \geq T'$

Observe que o problema descrito é idêntico ao problema da mochila que é provado ser NP-Completo. Logo, um algoritmo que solucione o nosso problema simplificado pode ser usado para resolver o problema da mochila. Concluimos, portanto, que o problema é NP-Completo [2] .

Heurísticas Avaliadas

Como mostrado na seção 5, o problema de replicação de objetos em redes CDN é NP-Completo. Portanto, apresentaremos e estudaremos quatro heurísticas [2] para o problema, dado que uma solução ótima não é conseguida em tempo polinomial.

Todas as heurísticas apresentadas trabalham com cópias prévias, citadas na seção 3. Porém, com pequenas alterações, é possível utilizá-las para trabalhar com cópias dinâmicas.

Para a descrição dos algoritmos, utilizaremos a seguinte notação: S_i - espaço disponível no AS_i para armazenamento de cópias, B - cojunto de objetos disponíveis para réplica, J - número total de objetos, I - número total de AS's e AS_OBJ - conjunto de todos os objetos copiados no AS_i.

Random - Neste algoritmo os objetos são atribuídos aos AS's de forma aleatória, sendo respeitadas as restrições de armazenamento. É utilizada uma distribuição uniforme de probabilidade para atribuir os objetos aos AS's. Um objeto pode estar armazenado em diversos nodos, porém nunca um nodo terá mais de uma cópia de um objeto [2] .

                       
for (i=1;i<=I;i++){ 
  AS_OBJ[i].size = 0;  
  while(AS_OBJ[i].size<S[i])
  { 
    obj=random();
     if (obj not in AS_OBJ[i].objs) and 
        (obj.size+AS_OBJ[i].size<=S[i])
     {  
       AS_OBJ[i].objs=AS_OBJ[i].objs U {obj}; 
       AS_OBJ[i].size+=obj.size;
     }
  }
}

Popularity - Nesta heurística, cada nodo armazena os objetos mais populares entre seus Clientes. Os nodos ordenam os objetos em ordem decrescente de popularidade e armazena o maior número de objetos que conseguir, respeitando a ordem de popularidade e sua restrição de capacidade de armazenamento [2] .

Um nodo pode estimar a popularidade de um objeto observando as requisições que ele recebe dos seus Clientes. Neste caso, o nodo não precisa de informações de outros nodos para decidir quais objetos vai armazenar.

       
for (i=1;i<=I;i++){
  AS_OBJ[i].size = 0;       
  while (AS_OBJ[i].size<S[i]){ 
     obj=ObtemMaisPopular(B[i],i);
     if (obj not in AS_OBJ[i].objs) and
        (AS_OBJ[i].size+obj.size<=S[i]){
       AS_OBJ[i].objs=AS_OBJ[i].objs U {obj}; 
       AS_OBJ[i].size+=obj.size;
     }
  }
}

Greedy-Single - Nesta heurística, cada nodo i calcula

C_ij=p_jid_ij(x₀) para cada objeto j.

Este custo representa a contribuição individual do objeto j em (1), considerando o posicionamento inicial dos objetos x₀. Após calcular C_ij para todos os objetos, ordena-se os objetos em ordem decrescente de C_ij, então armazena-se os objetos observando a ordem obtida e a restrição de espaço de cada AS. Desta forma, o AS precisa de informação da CDN para calcular d_ij. Como o custo C_ij é calculado somente uma vez, e com relação ao posicionamento inicial de cada objeto, a contribuição das cópias dos objetos para replicação dos próximos objetos, ainda não replicados, não é considerado [2] .

Logo, cada nodo armazena os objetos de forma independente dos outros nodos, ou seja, não existe cooperação entre os nodos da CDN. O algoritmo está descrito abaixo.

for (i=1;i<=I;i++) 
  for (j=1;j<=J;j++) 
    C[i][j]=P[i][j]*d[i][j](X[0]); 
    for (i=1;i<=I;i++){ 
      AS_OBJ[i].size = 0; 
      while (AS_OBJ[i].size<S[i]){ 
      obj = Max(C[i]);
      if (AS_OBJ[i].size+obj.size<=S[i]){
      AS_OBJ[i].objs=AS_OBJ[i].objs U {obj}; 
      AS_OBJ[i].size += obj.size;
    }
  }
}

Greedy-Global Nesta heurística, a CDN primeiro calcula

$C_{ij}=\lambda_{i}p_{ji}d_{ij}(x_{0})$ para cada objeto j e cada nodo i.

Então a CDN escolhe o maior C_ij e armazena o objeto j no nodo i. Com esta replicação, gera-se uma nova matriz de posicionamento X₁. Depois disto, a CDN recalcula os C_ij baseados nessa nova matriz de posicionamento e repete o processo anterior até que todos os AS's tenham sido preenchido com todos os objetos que puderem armazenar, respeitando sua restrição de espaço [2]. O algoritmo está descrito abaixo.

for (i=1;i<=I;i++) AS_OBJ[i].size = 0; 
k = 0;  
CalculaCij(X[0]);
while (Existe(AS_OBJ[i].size < S[i])){ 
  MaxCij( &obj, &i);
  if (AS_OBJ[i].size+obj.size<=S[i]){
    AS_OBJ[i].objs = AS_OBJ[i].objs U {obj}; 
    AS_OBJ[i].size += obj.size;
  } 
  k++;
  CalculaCij(X[k]);
}

Modelo de Simulação

O modelo de simulação utilizado foi baseado na topologia atual da Internet, que é segmentada em sistemas autônomos(AS's). Neste modelo, consideramos que cada AS possui um único servidor e um único Cliente da CDN.

A topologia de rede construída foi composta por 6 (seis) AS's e 6 (seis) servidores da CDN. A métrica utilizada em nossa avaliação, número de hops, nos permite ficar independente de problemas tais como a latência de rede, simplificando a avaliação efetuada.

O posicionamento inicial dos objetos nos servidores originais foi aleatório. Ou seja, primeiramente, geramos um determinada quantidade de objetos e os distribuímos aleatoriamente entre os diversos servidores. Foi considerado que todo o conteúdo do servidor original poderia ser replicado em algum servidor da CDN.

Cada servidor da CDN possui um buffer restrito para o armazenamento dos objetos. Este buffer variou de 0% a 50% do tamanho total de objetos em nossos experimentos. Ao considerarmos que o buffer pode armazenar 0% da quantidade total de objetos, estamos avaliando o comportamento da rede para o caso onde não existe uma rede de distribuição de conteúdo.

Para modelar o tamanho dos objetos utilizamos a distribuição de Paretto [11], com a limitação que o maior valor gerado é, no máximo, cinco vezes o tamanho médio dos objetos (fixado em 14 kb). Para definir a popularidade de cada objeto, utilizamos a distribuição de Zipf [12] (Valores de $\beta$ , 0.6, 0.8 e 1.0) . Como vimos anteriormente, a popularidade de um objeto é importante para o cálculo de distribuição nas heurísticas popularity, greedy-single e greedy-global.

A chegada de requisições em cada servidor segue uma distribuição uniforme. Optamos por considerar que cada servidor de um AS recebe o mesmo número de requisições. Desta forma, os servidores de cada AS apresentaram um comportamento semelhante, facilitando a análise final dos resultados obtidos. Os resultados de nossos experimentos encontram-se na seção 8.

Avaliação das Heurísticas

Em todos os experimentos, optamos por utilizar a estratégia de replicação prévia dos objetos. Esta escolha permitiu que o comportamento de cada heurística fosse mais facilmente avaliado, tendo em vista que a posição dos objetos permanecerá inalterada à medida que os usuários realizam suas requisições. Essa decisão fez com que a CDN se tornasse menos efetiva quando o buffer de seus servidores estivessem carregados com poucos objetos de tamanho grande, uma vez que os objetos replicados não são trocados entre os servidores, elevando, desta forma, o tempo de resposta dos usuários.

Para cada heurística, executamos os experimentos variando o valor do parâmetro beta da distribuição de Zipf (utilizada para modelar a popularidade dos objetos), o tamanho do buffer de cada servidor da CDN e o número de objetos armazenados nos servidores dos AS's.

Como podemos observar através dos gráficos 1, 2, 3 e 4, um pequeno acréscimo no tamanho do buffer , inicialmente, provoca um ganho significativo de desempenho do sistema. Entretanto, quando o buffer da CDN ultrapassa 35% da quantidade total de objetos, o ganho de desempenho passar a ser pouco significativo, decorrência do comportamento logarítmico dos gráficos.

**Figura 1:** experimento com 5000 objetos e $\beta$ =0.6
$\begin{figure} \centerline{ \epsfig {file=g5m06.eps,width=3.2in} }\end{figure}$

**Figura 2:** experimento com 5000 objetos e $\beta$ =1.0
$\begin{figure} \centerline{ \epsfig {file=g5m10.eps,width=3.2in} }\end{figure}$

É interessante observarmos que quando o parâmetro $\beta$ da distribuição de Zipf é igual a 1 (um), os algoritmos greedy-global, greedy-single e popularity apresentam um comportamento muito parecido pois, neste caso, a distribuição de Zipf se transforma numa distribuição uniforme.

Como pode ser visto nos gráficos, quando $\beta$ tem valor 0.6, a CDN é mais efetiva, ou seja, a contribuição para a redução do tempo de resposta dos usuários é maior. Isto ocorre porque quanto maior o valor de $\beta$ ( $\beta < 1$ ), menos objetos terão uma alta popularidade, fazendo como que a replicação dos mesmos resulte em uma redução significativa do tempo de resposta dos usuários. Nestes casos, onde um número menor de objetos tem uma baixa popularidade, a heurística random apresenta um desempenho pior, e no caso desta heurística replicar alguns destes objetos, a CDN contribuirá muito pouco para a redução do tempo de resposta dos usuários.

Observamos, por fim, que a heurística greedy-global obteve o melhor desempenho em todos os testes, e que as heuríticas popularity e greed-single tiveram comportamentos parecidos. Concluímos, ainda, que a heurística random tem o pior comportamento em todos os testes.

**Figura 3:** experimento com 10000 objetos e $\beta$ =0.6
$\begin{figure} \centerline{ \epsfig {file=g10m06.eps,width=3.2in} }\end{figure}$

**Figura 4:** experimento com 10000 objetos e $\beta$ =1.0
$\begin{figure} \centerline{ \epsfig {file=g10m10.eps,width=3.2in} }\end{figure}$

Conclusões e Trabalhos Futuros

Neste trabalho, estudamos o problema de distribuição de objetos em servidores CDN. Modelamos nossos experimentos de forma a encontrarmos um problema de otimização combinatorial, e provamos que o mesmo é NP-Completo.

Avaliamos quatro heurísticas para a replicação de objetos, utilizando o modelo proposto, e verificamos que a utilização dos mesmos implica num ganho significativo de desempenho do sistema. Ou seja, a utilização de técnicas de distribuição de objetos diminuem sensivelmente o tempo de resposta a uma dada requisição, assim como a carga de trabalho do servidor original.

Nossos resultados mostraram que a heurística Greedy-Global, onde os servidores da CDN trabalham cooperativamente, apresentou o melhor desempenho dentre as heurísticas avaliadas. Embora os algoritmos popularity e greedy-single tenham apresentado comportamento parecido acreditamos que, à medida que o número de nodos da rede CDN aumente, os resultados obtidos para estas heurísticas tendam a se distanciar.

A área de pesquisa relativa à avaliação e desenvolvimento de novos algoritmos para redes de distribuição de conteúdo possui um enorme potencial. Como trabalhos futuros, iremos investigar mais detalhadamente os mecanismos de cooperação entre os servidores, e avaliar o desempenho dos algoritmos quando consideramos uma replicação dinâmica dos objetos. Também pretendemos ampliar nosso modelo para que ele modele mais precisamente a topologia da internet e cosidere novos parâmetros, tais como o tráfego da rede e a carga dos servidores, possibilitando, desta maneira, que sejam estabelecidos limites inferiores para o desempenho destes tipos de algoritmos.

Bibliografia

1

Day, M., Cain, B. Tomplinson, G.
A Model for CDN Peering.
In IETF draft paper, number 17, November 2000.

2

J. Kangasharju and J. Roberts and K. Ross.
Object Replication Strategies in Content Distribution Networks.
In Proceedings of WCW'01: Web Caching and Content Distribution Workshop, June 2001.

3

Krishnamurthy B., Wills C. e Zhang Y.
On the Use and Performance of Content Distribution Networks.
In ACM SIGCOMM Internet Measurement Workshop 2001.

4

Cardellini, V., Casalicchio, E., Colajanni, M. and Yu, P.S.
The State of the Art in Locally Distributed Web-server System.
In Computer Surveys, volume 34, pages 263-311, June 2002.

5

Biliris, A. et al.
CDN - Brokering.
In Proceedings of The 5th International Web Caching and Content Delivery Workshop, June 2001.

6

Doyle, R.P., Chave, J.S., Gadde, S. e Vahdat, A.M.
The Tricke-Down Effect: Web Caching and Server Request Distribution.
In Sixth International Workshop on Web Caching and Content Distribution. Boston University, Boston, Massachusetts, USA., June 2001.

7

Akamai.
www.akamai.com.

8

Digital Island Inc.
www.digisle.net.

9

Thrupoint, M.L.
Content Delivery Networks (CDNs) - A Reference Guide.
In Cisco White Paper, 2001.

10

M. R. Garey and D. S. Johnson.
Computers and Intractability: A Guide to the Theory of NP- Completeness.
Freeman, 1979.

11

Gumbel, E.J.
Bivariate exponential distributions.
In Journal of the American Statistical Association, 1960.

12

G. K. Zipf.
Human Behavior and the Principle of Least-Effort.
Addison-Wesley, 1949.

13

Smith A., Ma F.K. e Rees D.
Content Distribution Networks and QoS.
In COMP9333 - Advanced Computer Networks Mini-Conference Report Topic 10, May 2002.

14

J. Kangasharju and J. Roberts and K. Ross.
Performance Evaluation of Redirection Schemes in Content Distribution Networks.
In Proceedings of The 5th International Web Caching and Content Delivery Workshop, June 2001.

15

Johnson, K. L., Carr, J. F., Day, M. S., and Kaashoek, M. F.
The Measured Performance of Content Distribution Networks.
In The 5th International Web Caching and Content Delivery Workshop, May 2000.

About this document ...

Algoritmos para Replicação de Objetos em Redes de
Distribuição de Conteúdo

This document was generated using the LaTeX2HTML translator Version 97.1 (release) (July 13th, 1997)

The command line arguments were:
latex2html -split 0 sem.tex.

The translation was initiated by Luiz Henrique Gomes on 9/25/2002

Footnotes

...objetos.: Este trabalho foi realizado como seminário da disciplina Projeto e Análise de Algoritmos - 1^o semestre de 2002. Prof.: Nívio Ziviani
...Zipf [12]: A lei de Zipf é utilizada para modelar diversas tipos de popularidades nas ciências sociais. Ex. frequências de palavras em textos, etc.
...1.0): Valores 0.6 e 0.8 são, tipicamente, encontrados em servidores cache [2]

Luiz Henrique Gomes
9/25/2002

Algoritmos para Replicação de Objetos em Redes de Distribuição de Conteúdo

Footnotes

Algoritmos para Replicação de Objetos em Redes de
Distribuição de Conteúdo