MIT 18.996 – Tópico da Teoria da Ciência da Computação: Problemas de Pesquisa na
Internet – Segundo Trimestre 2002
Aula 4 | 27de fevereiro de 2002
Palestrantes: T. Leighton, D. Shaw, R. Sudaran Redatores: K. Battochi e M. Monteleone
4.1. Introdução
Seria possível dizer simplesmente que o DNS é usado para encontrar algo na Internet. O
design tradicional (antigo) do DNS funciona essencialmente como um diretório de nomes e
números em que um usuário poderia digitar um nome e ter um número retornado (ou viceversa) de um arquivo de texto. Como se pode imaginar, esse sistema não era muito eficiente
e não funcionava muito bem na prática. Em vez de servir como um verdadeiro sistema de
nomes, ele era mais uma espécie de catálogo de placas.
O design atual do DNS não funciona exatamente como um catálogo de placas; em vez disso,
ele pode ser comparado a um diretório grande e distribuído. Há quatro termos importantes
que descrevem o layout básico do DNS:
1.
2.
3.
4.
Nome – inclui “.edu”, “.com”, “.org” etc.
Tipo – refere -se aos tipos de dados que estão sendo armazenados; os dados podem
ser de qualquer tipo, e não somente endereços.
Classe – com a exceção de algumas classes internas, classe simplesmente se refere
à Internet.
Dados – há vários tipos de dados. Exemplos: A (Endereço IP), CNAME (Alias), H-Info
(Informações de Host). É interessante observar que, por questões de segurança, não
há tanta divulgação a esse respeito como no passado, pois os usuários seriam
capazes de identificar informações sobre determinado computador e sua
localização.
4.2. Layout do DNS
Há 13 servidores raiz, cada qual com uma zona que define nomes de alto nível. Tome como
exemplo o diagrama a seguir, que ilustra a estrutura hierárquica do DNS:
RAIZ
4-1
Deve-se observar que o cache pesado é realizado em todas as etapas da árvore. Além disso,
as informações contidas em cada nó possuem um tempo de vida (TTL) associado a ele. Em
muitos casos, é de um dia mais ou menos, mas pode ser menos ou mais. Por questões
óbvias de eficiência, é útil para os servidores de nome economizar em largura de banda e,
essencialmente, em custo.
O proprietário de uma zona específica mantém um registro de todos as novas subzonas. Por
exemplo, veja o diagrama a seguir:
Math.mit.edu foi criado na rede do MIT; além disso, há três servidores de nome – x, y e z –
que pertencem ao departamento de matemática. O conceito de glue record descreve esse
tipo de delegação. Se uma zona é delegada a um servidor de nome cujo nome de host seja
descendente dessa zona específica, um glue record desse nome de host deve ser incluído
na delegação. Por exemplo, o Administrador do MIT mantém as informações sobre os
servidores de nome de matemática (isto é, as informações são mantidas como mit.edu em
oposição a math.mit.edu).
Vamos definir também alguns outros termos relevantes. Um registro PTR, ou registro de
ponteiro, também é conhecido como um registro inverso. Um registro PTR associa um
endereço IP a um nome canônico (o verdadeiro nome de um host). Os registros PTR devem
apontar para um nome que possa ser resolvido de volta para o endereço IP. O nome do
registro de ponteiro não é o próprio endereço IP, mas quatro octetos IP do endereço IP em
ordem inversa à seguida por IN-ADDR.ARPA. Por exemplo, 192.168.0.1 passa a ser
1.0.168.192.IN-ADDR.ARPA.
Antes de nos aprofundarmos no uso do DNS na prática, devemos analisar brevemente a
lame delegation (delegação imperfeita). Ocorre uma lame delegation quando um registro de
servidor de nome aponta para um host incorreto. Isso pode ocorrer quando uma zona é
delegada a um servidor que não foi corretamente configurado como de autoridade para a
zona. Da mesma forma, a lame delegation também pode ocorrer quando um servidor que
tem autoridade para a zona possui um registro de servidor de nome que aponta para outro
servidor que não tem autoridade para a zona. Isso faz com que os servidores não
respondam ou que não respondam de forma autoritária, o que resulta em tráfego na rede ou
em desnecessária carga de trabalho do servidor.
4.3 Usando o DNS na prática
Explicaremos como o DNS é usado na prática para baixar um site da Web. Também
detalharemos o processo de uma pesquisa de DNS quando ela ocorrer nesse contexto. É
útil saber que há duas formas de usar o DNS para baixar um site da Web: da maneira
tradicional e da maneira da Akamai. Descreveremos cada método em detalhes a seguir.
4-2
4.3.1 A Maneira Tradicional
Suponhamos que o usuário deseje visitar o web.mit.edu. Após inserir [1]http://web.mit.edu,
o navegador procurará resolver o endereço IP do site. O DNS tem seu papel aqui, visto que
mapeia o endereço web.mit.edu para o endereço IP 18.7.21.77. O DNS retorna o endereço IP
e o navegador entra em contato com o servidor nesse endereço. O servidor retorna, então, o
HTML (incluindo os links incorporados). Para cada objeto incorporado, o processo se
repete. Agora descreveremos o processo de pesquisa de DNS em mais detalhes.
Mencionamos anteriormente que o cache desempenha um papel importante nas pesquisas
de DNS. Dessa forma, quando o web.mit.edu é inserido no navegador, este consulta seu
próprio cache primeiro para ver se o nome em questão foi resolvido anteriormente. Se não
for encontrado no cache do navegador, o cache do sistema operacional será consultado. Se
não for encontrado, o navegador fará a conexão com seu servidor de nome local.
Novamente, o servidor de nome local retornará o endereço se ele tiver sido resolvido
anteriormente; caso contrário, ele consultará autoridades superiores. Na pior das hipóteses,
as consultas acabarão por alcançar um servidor DNS raiz. Depois que o endereço for
resolvido, o servidor DNS local entrará em contato com o servidor DNS do mit.edu para
obter a resolução para o web.mit.edu. Um endereço IP é recebido (e armazenado em cache)
e é passado de volta para o navegador dos usuários. Em seguida, a solicitação de HTML
tem início, conforme descrito no parágrafo anterior.
4.3.2 A Maneira da Akamai
É mais fácil baixar um site da Web que utilize tecnologia. O princípio básico de resolver um
endereço IP usando o DNS continua valendo, mas o endereço que é retornado da pesquisa é
de um servidor Akamai ótimo. O navegador entra em contato com o servidor Akamai para
solicitar HTML. O servidor Akamai é responsável por montar o site da Web e entregar o
conteúdo para o navegador dos usuários. Os servidores Akamai ótimos também seriam
responsáveis por entregar todos os objetos incorporados ao navegador. Agora
descreveremos o processo de pesquisa de DNS conforme aplicada à maneira da Akamai.
Como estamos modificando o procedimento de pesquisa de DNS para retornar o endereço
de um servidor Akamai ótimo, devemos desenvolver uma maneira de garantir que esse
servidor ótimo seja encontrado (em oposição à maneira tradicional pela qual o endereço IP
seria retornado para o site da Web solicitado). Um alias (nome alternativo) é então usado
para garantir que o endereço seja resolvido para o servidor ótimo apropriado. O processo
de pesquisa começa, então, com o servidor de nome local sendo direcionado para o
servidor DNS do site solicitado (seria o mit.edu do exemplo anterior; por questões de
consistência, partiremos do pressuposto que o site da Web do MIT utiliza a maneira da
Akamai para que possamos continuar a utilizá-lo como exemplo do caso da Akamai). Porém,
quando o servidor DNS do mit.edu é contatado, um alias chamado CNAME é fornecido ao
servidor de nome local. Esse é um nome de DNS intermediário (e não um endereço IP) que
depois será resolvido para o endereço IP do web.mit.edu. Por ora, o servidor de nome local
deverá resolver esse endereço de DNS. Vamos supor que o CNAME seja a123.b.akamai.net.
O servidor de nome local consultaria então o akami.net e receberia um endereço IP para um
servidor DNS Akamai de alto nível. Esse servidor resolveria o b.akamai.net. Agora, vamos
começar a perceber os benefícios da maneira da Akamai. O servidor DNS de alto nível agora
determina qual ende reço IP deve ser resolvido a partir do b.akamai.net, levando em
consideração questões geográficas. O endereço IP estabelecido é o endereço de um
servidor DNS da Akamai de nível baixo. O servidor DNS de nível baixo executa algoritmos
para otimizar o desempenho em tempo real, considerando fatores como congestionamento
da rede, cargas do servidor e condições da rede. Ele determina então o servidor da Web
ótimo para o usuário. No final, o servidor de nome local recebe o endereço IP de um
servidor Akamai ótimo que hospeda o conteúdo do site da Web solicitado. Como se pode
ver, a Akamai otimizou a maneira de entregar conteúdo pela Web por meio do
4-3
desenvolvimento de métodos engenhosos para downloads de sites da Web ótimos e
pesquisas de DNS.
4.4. Algoritmos BIND – Visão Geral
O objetivo geral dos algoritmos BIND é decidir qual o melhor servidor para respostas
rápidas e confiáveis (precisas). Começaremos com o algoritmo BIND 4. Vale a pena ilustrar
o algoritmo BIND 4 com um exemplo. Digamos que haja dois servidores de nome para
math.mit.edu: 1.2.3.4 e 1.2.3.5. Começamos consultando um, por exemplo, 1.2.3.4, e o
penalizamos toda vez que é consultado. A penalidade é proporcional ao tempo que ele leva
para fazer a consulta. Assim, 1,2,3.5 será consultado e penalizado da mesma maneira. O
processo continuará de forma que o servidor com a menor penalidade total seja o que é
consultado.
O algoritmo BIND 8 incorpora princípios semelhantes, mas introduz três fatores: a, ß e ?. O
fator a reflete o tempo de consulta. Ele é baseado 70% no tempo de consulta anterior e 30%
no tempo de consulta atual. Assim, a ajuda a determinar qual servidor dará a resposta mais
rápida. O fator ß trata da precisão. Ele penaliza os servidores que não respondem
corretamente, incluindo os servidores que são imperfeitos (lame). Por fim, o fator ? é
introduzido para garantir que todas as máquinas foram testadas. Ele diminui o tempo de
consulta de toda máquina que não tenha sido consultada. Dessa forma, ajuda a garantir que
servidores potencialmente rápidos e/ou precisos não serão rejeitados pelo algoritmo. Esses
três fatores devem permitir que o algoritmo BIND 8 tenha a expectativa de convergir no
servidor que responde rápida e precisamente. Agora trataremos dos algoritmos BIND e de
seu desempenho em mais detalhes.
4.5. Algoritmo BIND 4
O algoritmo BIND 4 tenta selecionar o servidor mais rápido, mas sem usar um servidor
exclusivamente, para que, se os padrões do tráfego mudarem, o servidor ótimo possa ser
encontrado. Ele procura fazer isso mantendo um total atualizado, o que inclui o tempo total
de todas as respostas até então. Para garantir que não será selecionado sempre o mesmo
servidor, o total também incluirá uma penalidade pelo fato de o servidor ter sido o
selecionado daquela vez.
Agora introduziremos uma notação para tornar as idéias mais precisas. Que N seja o
número de recursos que podemos consultar. Ri (t) será o total atualizado do recurso i antes
da etapa t e definiremos S i (t) como o tempo que o recurso i levaria para completar a
solicitação de t. Se definimos i*(t) como o recurso que nosso algoritmo escolherá para
consultar na etapa t, poderemos minimizar o desempenho médio
O algoritmo BIND 4 trabalha da seguinte maneira em cada etapa:
4-4
1.
2.
3.
i*(t) é selecionado para ser o i de forma que Ri(t) seja um mínimo (desfaz vínculos
arbitrariamente).
Ri*(t)(t + 1) ? Ri*(t)(t) + Si*(t)(t)
Todos os outros Ri permanecem inalterados.
Supondo que S i (t) sejam constantes em relação ao tempo, é fácil perceber que o melhor
desempenho possível é sempre selecionar o recurso com o menor S. Agora comprovamos
que BIND 4 é N-competitive.
Teorema 4.1. Supondo que Si seja constante, o algoritmo BIND 4 descrito acima é executado
com tempo médio
Prova: Digamos que ni (i) seja o número de vezes que o recurso i seja selecionado antes da
etapa t. Depois, como S i são constantes, Ri (t) = S i ni (t). Considere dois recursos, i e j. Após t
etapas, o recurso i será escolhido se Ri (t) for inferior a Rj (t), o que implica Si ni (t) < S j nj (t). Se
a desigualdade inversa for mantida, j será escolhido. Assim, a proporção do número de
vezes que i é escolhido em relação ao número de vezes que j é escolhido tenderá a ni (t)/nj (t)
= S j /S i , e o recurso i será escolhido um número de vezes inversamente proporcional a S i .
A probabilidade de um dado recurso ser escolhido é c/S i para alguns c. A probabilidade total
é 1, e ntão
e
. Para calcular T, observe que o recurso i será
selecionado com a probabilidade c/Si e levará S i tempo para ser executado. O tempo de
execução esperado é, portanto,
O fator de N no tempo médio de execução é preocupante, pois o algoritmo ideal selecionaria
o recurso mais rápido todas as vezes, independentemente de quantos recursos há. É
concebível que a soma no denominador possa resolver esse problema. Nós demonstramos
que não é o caso.
Teorema 4.2. Para todo ? maior que zero e todo N, há um conjunto de recursos de forma que
o tempo de execução esperado do algoritmo BIND 4 seja no mínimo N(1 – ?) vezes o
algoritmo ótimo.
Prova: Defina
e
fornecido pelo Teorema 4.1 é
para
. Depois, o desempenho médio
2
Da identidade (1 – ?) (1 + ?) = 1 – ? , deduzimos que (1 – ?) (1 + ?) = 1 e que, para ?, na faixa
(0, 1), 1/(1 + ?) = 1 – ?. Assim, T = N(1 – ?), apesar de que o algoritmo ótimo sempre
escolheria o recurso com o tempo de execução 1.
4-5
Não só é possível o tempo médio do BIND 4 aumentar quando o número de recursos
também aumentar, como é provável que ocorra na prática o exemplo utilizado na prova do
Teorema 4.2. Se houver um recurso próximo e vários na parte oposta, os tempos de
desempenho serão muito mais parecidos com os usados na prova.
Nesse ponto, consideraremos uma alteração mínima no algoritmo BIND 4. Em vez de definir
Ri*(t)(t + 1) = Ri*(t)(t) + S i*(t)(t) como no algoritmo original, o que ocorrerá se definirmos Ri*(t)(t +
1) ? Ri*(t)(t) + ƒ(S i*(t)(t)) para uma função ƒ diferente da identidade? Parece que poderemos
2
obter um algoritmo competitivo se usarmos, por exemplo, ƒ(x) = x ou certamente com ƒ(x) =
x
2 . Para resolver essas questões, precisamos comprovar primeiro o teorema a seguir.
Teorema 4.3. Com R definido como acima, o tempo médio de operação T do algoritmo BIND
4 modificado é
Prova: Esta prova é praticamente igual à prova do Teorema 4.1. A probabilidade de o
recurso ser selecionado agora é proporcional a 1/S i . A constante de proporcionalidade deve
ser 1/ ? i ƒ(S i ) para fazer as probabilidades chegarem a um. Como o recurso i leva S i tempo
para ser executado, o desempenho esperado do algoritmo é
Quanta diferença há entre os algoritmos BIND 4 novo e antigo? Primeiro comprovaremos
que toda função assintoticamente pior que a usada no BIND 4 original é muito ruim.
Teorema 4.4. Se
for uma função de tal forma que lim inf(ƒ(x)/x) = 0, o
desempenho do novo algoritmo poderá ser arbitrariamente ruim.
Prova: É claro que, se ƒ(x) for menor ou igual a zero para alguns x maiores que zero, o
desempenho do algoritmo poderá ser abaixo do ótimo um fator arbitrariamente maior.
Portanto, suponha para o restante da prova que ƒ(x) seja positivo para todos os x positivos.
Suponha que ƒ tenha um propriedade que lim inf(ƒ(x) < 8. Para mostrar que o desempenho
pode ser pior que qualquer número fixo A, considere N como 2. Use Si = 1. Há x
arbitrariamente grandes de forma que ƒ(x) < L, então considere S2 de forma que
com ƒ(S 2) < L. Então
Após algumas contas, obtemos
4-6
Reunindo os termos em A, obtemos
Daí, imediatamente se segue que
então, realmente é possível obter arbitrariamente um desempenho ruim, independentemente
do número de fontes.
Suponha que lim inf ƒ(x) = 8. Então, para um x suficientemente grande, ƒ(x) > 1. Para todo A,
considere novamente N = 2 e defina S 1 = 1. Como lim inf ƒ(x)/x = 0, se ocorrer de qualquer n0
e c ser maior que zero, haverá um x maior que n0 de tal forma que ƒ(x) < cx. Sendo c = 1/C,
isso é equivalente a dizer que, para todo C, há um x > n 0 de forma que x/ƒ(x) > C. Como lim
inf ƒ(x) = 8, há alguns n0 de tal forma que, para todo x maior que n0, ƒ(x) > 1. Então, tome S 2
como um número maior que n0 para o qual S2/ƒ(S2) > (A – 1)/ƒ(1) + A. Então, como ƒ(S2) > 1,
ocorre que
Mas, como
e
Então
Eliminando os denominadores, obtemos
termos em A,
Reunindo os
. Dividindo isso, obtemos
Dividindo o numerador e o denominador por ƒ(1)ƒ(S 2), obtemos
de forma que agora comprovamos nosso resultado em toda a sua generalidade.
4-7
De certa maneira, isso demonstra que o algoritmo realmente usado pelo BIND 4 não é tão
ruim, visto que pelo menos o desempenho de pior caso é limitado por N. Escolher uma
penalidade assintoticamente inferior a S i pode levar a um desempenho extremamente ruim.
O que ocorrerá se escolhermos uma penalidade maior? Conseguiremos obter o
desempenho médio para chegarmos até o resultado ótimo? A resposta é que podemos
chegar muito próximo do desempenho ótimo, mas nunca chegaremos até ele.
2
Para motivar essa discussão, tomemos como exemplo o que ocorre quando ƒ(x) = x . De
forma semelhante ao que fizemos para comprovar o Teorema 4.2, considere S i = 1 e S2 = S3 =
... =
. Então
Assim, o desempenho ainda depende de N, apesar do aumento da penalidade. Podemos
fazer uma análise semelhante para qualquer função com um inverso definido de forma
apropriada.
Teorema 4.5. Dada uma função bijetora
, há um conjunto de Si tal que o novo
algoritmo BIND 4 é executado no tempo médio
competir.
Prova: Considere Si = 1 e
com o qual não há como
para
. Então
Assim, apesar de obtermos um desempenho que cresce arbitrariamente de forma lenta com
N, não podemos obter um desempenho que seja independente de N.
Podemos estender esse resultado a funções que satisfaçam a condições menos rigorosas
que as do Teorema 4.5.
Teorema 4.6. Dada uma função
, há um conjunto de S i tal que o algoritmo é
executado em um tempo arbitrariamente ruim.
Prova: Se lim inf ƒ(x)/x = 0, isso é conseqüência imediata do Teorema 4.4. Então suponha
que lim inf ƒ(x)/x seja positivo. Há alguns c e alguns n0 de forma que, para todo x > n0, ƒ(x) >
cx. Defina
Considere
e
como o maior x de tal forma que
. Então,
e
e
,
4-8
para
.
. Assim, se
Mas
e
. Assim,
Mas, se
para
, então
aumentará até o infinito, e T crescerá até o
infinito com N, como deveria ser comprovado.
4.6 Algoritmo BIND 8
Conforme já mencionado, o algoritmo BIND 8 funciona de forma um tanto semelhante ao
BIND 4. No entanto, ele usa três fatores para determinar o desempenho. As equações que
orientam a atribuição de uma penalidade em t são as seguintes:
1.
Se o recurso i não for selecionado para ser consultado, Ri (t + 1) = ?Ri (t).
2.
Se o recurso i for selecionado para ser consultado e retornar uma resposta correta,
. Lembre-se de que a notação i*(t) indica o
recurso escolhido para ser consultado na etapa t.
3.
Se o recurso i for selecionado, mas não conseguir retornar uma resposta aceitável,
.
Como já mencionado, o código BIND 8 usa a = 0,3, ß = 1,2 e ? = 0,98. Esse algoritmo parece
intuitivamente selecionar o servidor mais rápido na maioria das vezes, mas demonstramos
que, na verdade, seu desempenho pode ser arbitrariamente ruim.
Teorema 4.7. Há um conjunto de dois recursos, de forma que o desempenho do algoritmo
BIND 8 é pior que o N-competitive.
Prova: Suponha que S i = 1 para todo t e S 2 = x para todo t, onde x é um número fixo. Então,
2
suponha que o recurso 2 seja selecionado. R2 será x, ?x, ? x etc. em cada etapa sucessiva,
n
visto que R1 será selecionado todas as vezes. Uma vez que ? x seja inferior a um, x será
n
selecionado novamente. Mas ? x = 1 é igual a
. Então, o tempo de execução
médio do algoritmo é aproximadamente
, que pode claramente aumentar
conforme nossa vontade, bastando para isso que se escolha um x apropriado.
4-9
Bibliografia
[1] Akamai Whitepaper: “Internet Bottlenecks: the Case for Edge Delivery Services”. 2000,
Cambridge, MA. URL disponível:
http://www.akamai.com/em/html/services/white_paper_library.html.
[2] Leighton, Tom; Shaw, David; Sudaran, Ravi. Apresentação: “DNS”. 2002, Cambridge, MA.
4-10