1
INFRAESTRUTURA
Capítulo 5
Crovella, M, Krishnamurthy, B. Internet Measurement: infrastructure, traffic & applications. John Wiley &
Sons, 2006.
Roteiro
2




Propriedades
Desafios
Ferramentas
Estado da Arte
3
Propriedades
Propriedades
4


Nesta seção são revistas as propriedades
importantes da infraestrutura da Internet.
Nossa abordagem será “bottom-up”:
 Propriedades
físicas dos componentes
 Topologia (interconexão dos componentes)
 Caminhos na Internet (rotas)
 Interação do tráfego com a infraestrutura física
Links
5



Visto da camada IP, o progresso de um pacote através da rede consiste da
passagem de nó para nó por uma sequência de etapas.
Cada etapa pode ser considerada um link.
Um link pode ser:




Propriedades de interesse:



Um meio de transmissão ponto a ponto
Sequência de conexões comutadas abaixo da camada IP
Meio de difusão
Atraso de propagação
Capacidade
Propriedades de desempenho:



Atraso dos pacotes
Perda de pacotes
Jitter (variação do atraso)
Roteadores
6

Roteadores movem pacotes de um link de entrada
para um link de saída.
Roteadores
7

Organização interna do motor de encaminhamento:

Estratégias para os buffers de saída:
 Disciplina
de serviço drop-tail
 Gerenciamento ativo de filas
Roteadores
8



Muitas técnicas de medição de rede dependem da
obtenção de respostas dos roteadores.
Os detalhes da arquitetura interna podem afetar o
tempo gasto para a geração de respostas.
Em particular, o tempo necessário para um roteador
responder a uma mensagem de um protocolo como
um pacote ICMP pode ser substancialmente
diferente do tempo que ele leva para repassar um
pacote.
Roteadores
9

Propriedades que temos interesse de medir:
 Ponto
de vista estático:
 Endereços
IP usados nas interfaces dos roteadores
 Localização geográfica do roteador
 Tipo particular do roteador
 Variantes dos protocolos suportados
 Ponto
de vista dinâmico:
 Tempo
necessário para responder a uma mensagem ICMP
 Tempo necessário para repassar um pacote.
Sem Fio
10


As conexões sem fio normalmente são usadas
apenas como tecnologias de acesso e não fim-afim.
A escolha da tecnologia sem fio determina:
 Alcance
máximo,
 Taxa de transferência de dados,
 Confiabilidade
 Interferência potencial
 Número de usuários concorrentes
Tecnologias Sem Fio
11

Família 802.x
 Wi-fi

Bluetooth
 PAN

– Personal Area Network
WiMAX
Medições envolvendo Comunicação
Sem Fio
12





Força do sinal
Potência consumida
Taxa de transferência de bits
Grau de cobertura
Informações relacionada com a sessão:
Duração
 Tempo de estabelecimento da conexão
 Lista das aplicações usadas
 Handoffs entre pontos de acesso (caso haja algum)
 Taxas de erros

Medições Tradicionais
13

Capacidade do link:
 Em
rede sem fio ela muda com o tempo devido a
mobilidade do usuário, obstruções físicas, tráfego
cruzado na mesma frequência, etc.




Largura de banda disponível e efetiva
Identificação de links gargalo
Etc.
As medições tendem a ser complicadas pela
combinação de redes cabeadas e sem fio.
Propriedades da Topologia
14

A interconexão de componentes da Internet pode
ser visualizada em quatro níveis:
 Sistema
autônomo (AS)
 Ponto de presença (PoP)
 Roteador
 Interface
Topologia: Interconexão de ASes
15




A interconexão de ASes forma um grafo conhecido
como grafo AS.
Neste grafo os vértices são os ASes e
As arestas conectam ASes que trocam tráfego
diretamente.
Esta é a visão mais grosseira da topologia da
Internet.
Topologia: Interconexão de PoPs
16



Dentro de um AS, os roteadores são
frequentemente reunidos em localidades físicas
identificáveis, chamadas de pontos de presença
(PoPs).
Um PoP consiste de um ou mais roteadores num
único local.
Um grafo neste nível (PoP) é normalmente a visão
mais detalhada que um ISP disponibiliza
publicamente.
Topologia: Grafo de roteadores
17

Neste grafo:
Os vértices são roteadores, e
 As arestas são conexões de uma etapa entre roteadores.




É importante distinguir entre uma conexão em uma
etapa de um link físico ponto a ponto.
Pode-se associar a cada aresta (link) o seu atraso de
propagação e capacidade.
E os vértices podem ser rotulados com sua localização
física e AS proprietário. Pode ser útil rotulá-los também
com a identificação do PoP correspondente.
Topologia: Grafo de interfaces
18


Fornece a visão mais detalhada.
Neste grafo:
 Vértices
são interfaces de roteadores e
 Arestas são conexões de uma etapa.


Este grafo é importante por ser diretamente
medido pela ferramenta traceroute
Um grafo de roteador pode ser obtido do grafo de
interfaces agrupando os vértices de interfaces
associados a cada roteador.
Interação do Tráfego com a Rede
19

Certos aspectos da estrutura da rede restringem as
propriedades de tráfego:
 Menor
atraso possível
 Vazão máxima possível
Atraso de Pacotes
20

O atraso experimentado por um pacote ao passar
pela rede corresponde à soma da contribuição de
diversos fenômenos:

Atraso de Roteamento
Atraso de processamento do pacote
 Atraso de enfileiramento
 Outros atrasos


Atraso de Transmissão


𝑠/𝑡 onde 𝑠 é o tamanho do pacote e 𝑡 é a capacidade do link
Atraso de Propagação

𝑑/𝑣 onde 𝑑 é a distância física e 𝑣 é a velocidade de
propagação
Atraso de Pacotes
21




O atraso de pacotes é uma métrica aditiva.
Cada um dos fenômenos listados anteriormente
potencialmente ocorrem em cada etapa ao longo de
um caminho.
Os atrasos por etapa são aditivos ao longo de um
caminho.
Dado um conjunto de atrasos por etapa 𝑑(ℎ) e uma
matriz de roteamento 𝐺 = 𝐴𝑇 , podemos expressar o
conjunto de atrasos por caminho 𝑑(𝑝) como sendo 𝑑(𝑝)
=𝐺 𝑑(ℎ) .
Perda de Pacotes
22

Causas:





Descarte explícito por um elemento de rede, ou
Descarte por erro de transmissão identificado pela verificação de erros.
A fonte mais significativa de perda de pacotes é o
congestionamento.
A perda explícita de pacotes poderia ser caracterizada como um
processo de chegada de eventos de descarte. No entanto,
normalmente é difícil obter informações sobre os instantes das
perdas.
Portanto, as perdas são normalmente caracterizadas como uma
série temporal de contagens. E a quantidade de perdas por
unidade de tempo podem ser interpretadas como estimativas das
taxas de perdas de pacotes.
Perda de Pacotes
23

A medida mais comum é a taxa relativa de perda de pacotes:
fração de pacotes perdidos durante um certo intervalo de tempo:


A perda relativa de pacotes ao longo de um caminho (assumindo
independência das perdas) é dada por:


ℓ𝑛 = 𝐿𝑛 /𝐶𝑛 onde 𝐶𝑛 é o número de pacotes que entraram no
elemento de rede no período de tempo 𝑛 e 𝐿𝑛 é o número de pacotes
perdidos neste mesmo intervalo de tempo.
ℓ𝑛 = 1 −
𝑖(1
− ℓ𝑛,𝑖 )
Que pode ser convertida para uma relação linear usando
logaritmos:

Seja 𝑙(ℎ) = log 1 − ℓ(ℎ)

Então log 1 − ℓ(𝑝) = 𝑙(𝑝) = 𝐺 𝑙(ℎ)
Vazão (Throughput)
24




Taxa na qual o tráfego pode fluir através da rede.
Limitada pelos limites de capacidade dos elementos de
rede e pelo congestionamento.
Considerando um intervalo de tempo 𝑇 grande o
suficiente em relação ao tempo necessário para
atravessar um caminho da rede, então a vazão do
caminho durante o período 𝑛 pode ser estimado como
𝐶𝑛 /𝑇, onde 𝐶𝑛 corresponde ao número de pacotes que
atravessam o caminho sem perdas.
O recíproco da vazão é o 𝑇/𝐶𝑛 é o intervalo de tempo
médio entre chegadas de pacotes durante o intervalo
𝑛.
Vazão
25




A vazão pode ser expressa também em bytes por
unidade de tempo: 𝐵𝑛 /T
A vazão através de uma sequência de etapas é
determinada pelo elemento com a menor capacidade
disponível.
O gargalo pode ser um sistema final ou um dos
elementos internos à rede.
Limitando a restrição aos elementos internos, a vazão
em um conjunto de caminhos 𝑡(𝑝) é determinada pela
capacidade por etapa 𝑡(ℎ) por 𝑡(𝑝) = 𝐺 𝑡(ℎ) , onde a
multiplicação da matriz é efetuada usando a álgebra
(min,×)
Jitter de Pacotes
26



É uma medida da suavidade do processo de
chegada de pacotes e pode ser expresso como a
variabilidade do intervalo de tempo entre
chegada de pacotes.
O jitter pode ocorrer devido à variação no tempo
dos atrasos das filas nos roteadores ao longo do
caminho.
Chegada de pacotes com baixo jitter são mais
previsíveis e leva a um desempenho na camada de
aplicação mais confiável.
Jitter
27



A caracterização do jitter requer medições dos
intervalos entre chegadas.
Uma caracterização completa é dada pelo
processo entre chegadas 𝐼𝑛
Medidas mais econômicas e mais usadas são os
momentos da distribuição 𝐼𝑛 , a variância dos
intervalos entre chegadas, por exemplo.
Conexões
28




Podem ser importantes medidas de taxa de perda de
pacotes, atraso de pacotes e vazão para conexões
individuais, por exemplo para o TCP.
Como a taxa média de pacotes do TCP depende do
tamanho da sua janela e do tempo de ida e volta
(RTT), medidas de RTT de uma conexão pode ser muito
valiosa.
Como há retransmissões, nem todos os bytes recebidos
são repassados para a aplicação.
Chamamos de goodput à taxa na qual a aplicação
recebe dados com sucesso.
29
Desafios
Desafios
30




Simplicidade do Núcleo
Camadas Escondidas
Pedaços Escondidos
Barreiras Administrativas
Simplicidade do Núcleo
31





Os elementos de comutação da Internet são projetados
para ser “sem estados” em relação às conexões e fluxos
que passam por eles.
Este princípio de projeto permitiu aos roteadores Internet
ser muito simples.
Qualquer forma de instrumentação, mesmo simples
contadores por pacote ou por byte, adicionam custo e
complexidade ao projeto.
Isto prejudica a observabilidade em muitos pontos da rede.
Medições de atraso e perda de pacotes assim como vazão
são fornecidos apenas de forma agregada através do
SNMP. Para a obtenção de medições detalhadas seria
necessária uma captura de pacotes.
Camadas Escondidas
32



Abaixo da camada IP a transmissão de pacotes pode
ser implementada de formas muito diferentes.
Estes detalhes estão escondidos no nível do IP. Nem
mesmo a captura de pacotes pode detectar estas
diferenças.
Pacotes que passam por uma etapa do IP podem na
verdade estar passando por:
Um enlace sem fio com sinalização complexa e
retransmissões na camada de enlace
 Caminho comutado por rótulos envolvendo diversos
elementos de comutação de nível 2.
 Redes ópticas...

Pedaços Escondidos
33


O argumento fim-a-fim indica que certas funções
devem ser executadas apenas nos sistemas finais.
No entanto, há diversos dispositivos que desviam deste
princípio:


Coletivamente chamados de middleboxes: firewalls,
tradutores de endereços e proxies
Razões para o uso de middleboxes:
Segurança
 Gerenciamento
 Desempenho
 Tradução de endereços

Pedaços Escondidos
34

Cada um destes tipos de middleboxes impede a
visibilidade de alguns componentes da rede.
 Firewalls
bloqueiam pacotes UDP ou ICMP usados pelo
traceroute.
 NAT pode impedir a descoberta de sistemas finais via
ping.
Barreiras Administrativas
35


ISPs normalmente escondem os detalhes de suas
redes do público externo.
Detalhes de configuração de roteadores
individuais, padrões de interconexão, e a
quantidade de tráfego transportado nos links são
todos considerados sensíveis à competição.
Barreiras Administrativas
36

Os ISPs bloqueiam tráfego que possa ser usado para
medir a infraestrutura:
Pacotes de eco ICMP são bloqueados nos roteadores de
entrada
 Tentativas de estabelecer conexões SNMP são bloqueadas.
 Informações fornecidas como as de topologia são
normalmente simplificadas.


Portanto, pode ser difícil obter uma figura detalhada
de porções da infraestrutura da Internet simplesmente
porque os ISPs procuram ativamente esconder estes
detalhes.
37
Ferramentas
Ferramentas
38

Medições Ativas:
 Adicionam
tráfego na rede para obter as medições
desejadas

Medições Passivas:
 Captura
de dados gerados por outros usuários e
aplicações e não pelo processo de medição
Ferramentas de Medições Ativas
39




Ping
OWAMP
Traceroute
Medições de Largura de Banda (adiante)
Ping
40


Envia um pacote ICMP de Eco para o destino e captura
o pacote de Resposta do Eco.
Útil para:
Checar a conectividade até o destino
 Medir o atraso de ida e volta (RTT – round trip time) entre o
transmissor e o destino.



Vantagem: o destino apenas responde da sua forma
normal (não precisa estar instrumentado).
Desvantagem: em caso de congestionamento, não dá
para identificar se ocorre na ida, na volta, ou em
ambos.
OWAMP
41




One-Way Active Measurement Protocol
Definido na RFC 4656
Necessita de relógios sincronizados ou um método
para remover o offset e skew dos relógios a partir
das medições.
Elementos:
 Protocolo
de controle
 Protocolo de teste
 Implementação de ambos os protocolos
OWAMP: Resultados obtidos
42

Métricas:
 Atraso
em um sentido (OWD – One Way Delay)
 Pacotes perdidos em um sentido
 Variação do atraso em um sentido

Outros Resultados:
 Pacotes
duplicados
 Reordenamento de pacotes (pacotes fora de ordem)
 Número de Hops (indicação de alteração)
OWAMP: Protocolo de Controle
43




Implementado usando o TCP
Utiliza a porta 861
Suporte a AA
Utilizado para:

Configurar os testes
Número de portas controladas no receptor (EndPoints)
 Agenda de envio extremamente configurável
 Permite alterar o tamanho dos pacotes
 Marcar DSCP, etc.

Inicializar a conexão, iniciar e parar os testes
 Receber os resultados


Possibilidade de receber resultados parciais de uma medição
OWAMP: Protocolo de Teste
44




Responsável pela execução dos testes
Utiliza o UDP
Utiliza portas aleatórias > 1024 para executar os
testes
As sessões podem ser:
 Não
autenticadas (“Open”)
 Autenticadas, ou
 Criptografadas
OWAMP: Arquitetura
45
Traceroute
46


O campo de TTL (Time To Live) do cabeçalho do IP
é decrementado de um toda vez que um pacote
passa por um roteador.
Se o contador chegar a zero, o protocolo IP requer
que o pacote seja descartado e seja enviada uma
indicação de erro para o remetente original,
através de um pacote ICMP TIME EXCEEDED.
O
endereço origem deste pacote é a interface do
roteador que descartou o pacote original.
Traceroute
47

Portanto, se um pacote que possui um pacote com o TTL
setado para 𝑛 for enviado para um determinado
destino, o roteador que estiver a uma distância 𝑛 no
caminho poderá ser identificado pelo pacote ICMP
TIME EXCEEDED desde que o caminho até o destino
possua mais do que 𝑛 etapas.
Traceroute
48

Dificuldades:
 Assimetria
dos caminhos de ida e de volta
 Caminhos instáveis e falsos enlaces
 Roteador
 Resolução
com Balanceamento de Carga
de apelidos (identificação de duas
interfaces que pertencem ao mesmo roteador)
 Carga da medição
Assimetria dos caminhos de ida e de
volta
49


Os nós visitados pelo traceroute são aqueles
encontrados no caminho de ida (forward) da origem
até o destino.
Estes não são necessariamente os mesmos nós do
caminho reverso!
Caminhos instáveis e falsos enlaces
50


Se os caminhos não forem estáveis durante o período
de medição, então pacotes de teste seguirão caminhos
diferentes.
Isto leva a uma inferência da existência de um caminho
𝐴 → 𝐵 → 𝑌, ou seja um falso link entre 𝐵 e 𝑌!
Roteador com Balanceamento de
Carga
51

Resultado: Caminhos inexistentes e falsos links.

Solução: Paris Traceroute

www.paris-traceroute.net
Paris
Traceroute
52



Balanceadores de carga por fluxo usam os campos em
amarelo para identificar um fluxo.
As setas vermelhas mostram os campos incrementados
pelo traceroute clássico.
O Paris Traceroute usa os campos em verde para
identificar os pacotes de teste.
Resolução de apelidos
53




O traceroute descobre interfaces e não
roteadores.
Cada roteador possui múltiplas interfaces.
Mas, nem sempre está claro que interfaces
pertencem ao mesmo roteador.
Foram propostos diversos métodos para descobrir
se duas interfaces pertencem ao mesmo roteador.
Métodos para a
Resolução de apelidos
54

Envio de pacotes de Eco ICMP para ambas as
interfaces a partir do mesmo roteador.
 Se
ambas pertencerem ao mesmo roteador, as
respostas serão enviadas a partir da mesma interface.
 Casando as mensagens de Eco que possuem a mesma
interface de origem pode-se inferir que os pacotes de
Eco originas foram enviados do mesmo roteador.
Métodos para a
Resolução de apelidos
55

Uso dos campos de identificação e TTL:
 Como
o campo de identificação é normalmente
incrementado, dois pacotes que venham do mesmo
roteador têm a tendência a ter campos com valores
próximos.
 Além do mais, pacotes que vierem do mesmo roteador
ao chegarem a um ponto comum devem ter o mesmo
valor de TTL.
 Portanto,
se dois pacotes chegarem num ponto de medição
com valores de TTL diferentes, é uma indicação de que são
originados em diferentes roteadores.
Métodos para a
Resolução de apelidos
56

Uso da opção de Registro de Rota:
 Os
roteadores que dão suporte a esta opção irão
inserir o endereço da interface através da qual o
pacote foi transmitido no cabeçalho do pacote durante
o processo de encaminhamento.
 Esta interface é frequentemente diferente da que
aparece no pacote de resposta de Eco do ICMP.
 Isto permite que as duas interfaces sejam associadas
com o mesmo roteador.
Métodos para a
Resolução de apelidos
57

Adivinhação(!):
 Por
facilidade de gerenciamento, os links entre dois
roteadores normalmente recebem endereços que
diferem um do outro por apenas uma unidade:
 200.0.0.1
e 200.0.0.2
Carga da
medição
58




Na figura acima, o link de A a B é atravessado três
vezes.
Em geral o traceroute pode impor uma carga
considerável e alguns links sobretudo para a
descoberta de topologia em grande escala.
Disparando testes de uma fonte para diversas origens
provoca uma carga excessiva em links próximos à
origem.
Disparando testes de múltiplas fontes para o mesmo
destino, tende a impor uma carga pesada nos links
próximos ao destino.
Carga da
medição
59

Para otimizar o uso foram propostas algumas
ideias:
 Rastrear
as interfaces que já foram visitadas e parar
os testes quando se encontrar uma interface já visitada
 Assume
que as rotas sejam estáveis e que haja um único
caminho de modo que formem uma árvore.
 No
caso de múltiplas fontes é preciso trocar
informações entre as origens sobre nós anteriormente
vistos.
Traceroute: outros usos
60



O traceroute pode ser usado também para
descobrir a topologia em termos de ASes.
A ideia básica é determinar a que AS pertence
cada um dos roteadores ou interfaces que estão no
caminho descoberto.
O mapeamento entre interfaces e ASes podem ser
extraídos de registros de rotas ou a partir de
tabelas BGP, mas elas devem ser usadas com
cuidado.
Outros Métodos Ativos
61



Outra ferramenta útil para a medição de redes ativa é o
multicast.
Dado que uma única cópia é replicada pelos roteadores ao
longo do caminho, as condições de rede experimentadas
por um único pacote são refletidas nas propriedades
mensuráveis das múltiplas cópias do pacote.
Pacotes enviados aproximadamente no mesmo tempo pelo
mesmo caminho experimentam condições de rede
semelhantes.


Se dois pacotes são enviados próximos e um deles se perde, o
outro fornece informações úteis sobre as condições da rede
experimentada pelo pacote perdido.
Esta mesma ideia pode ser usada para inferir o tamanho das
filas em roteadores de acesso.
Suporte do Sistema a Medições Ativas
62



Muitos métodos de medição ativa envolvem a injeção
de pacotes arbitrários na rede, ou na captura de
pacotes arbitrários na rede.
Acesso irrestrito às interfaces de rede levanta questões
de segurança e os administradores de rede
frequentemente hesitam em garantir este acesso.
Além do mais, a injeção eficiente de pacotes e a
medição precisa dos instantes de partida e chegada é
feito mais facilmente ao nível do kernel do SO.

Por isto, foram definidos bibliotecas e interfaces de sistema
especializados para a medição ativa de redes.
Medições Passivas
63



A medição passiva consiste em capturar tráfego
que foi gerado por outros usuários e aplicações e
não pelo processo de medição.
O uso mais comum da medição passiva de tráfego
é entender as propriedades do próprio tráfego e,
portanto, será coberto no Capítulo 6.
Nesta seção o foco é apenas em métodos passivos
para a medição da infraestrutura que consiste
geralmente na captura e análise do tráfego do
plano de controle (roteamento).
BGP
64

Tabela de roteamento BGP provê informação
parcial sobre a topologia entre ASes.
BGP
65

Vantagens:
 Grande
conjunto de conexões AS-AS que se aprende
apenas processando visões do BGP.

Desvantagens:
 Todos
os caminhos formam uma estrutura como uma
árvore, com raiz no AS alvo. Mas, nenhuma conexão
cruzada existente é descoberta (porque não são
usadas pelo roteamento até o prefixo alvo).
 Agregação de rotas e filtragem tende a esconder
certas conexões entre ASes.
BGP
66

Desvantagens:
 Muitos
ASes (especialmente os de tier 1) possuem
múltiplas conexões físicas.
 Grandes ISPs fazem conexões com outros em diversas
localidades por questões de eficiência e redundância.
No entanto, apenas uma aresta entre os dois ASes irá
aparecer no gráfico resultante.
Obtenção de dados do BGP
67


Além dos dados do routeview, é possível obter
atualizações do BGP diretamente registrando-se para
recebê-las através de uma sessão com um roteador que
fale BGP (vide detalhes na seção 6.3.1).
Dificuldades:
Pode não ser possível obter atualizações no ponto de
interesse.
 A visão local obtida é necessariamente incompleta
 Anomalias de roteamento e ‘ruído’ podem dificultar inferir o
estado real do sistema de roteamento interdomínio.

OSPF
68


É possível obter passivamente medições de
infraestrutura dentro de um AS, capturando tráfego
gerado pelo plano de controle através dos
protocolos de roteamento interno (IS-IS ou OSPF).
No caso do OSPF pode-se capturar anúncios dos
estados dos enlaces dentro de um domínio de
roteamento.
 No
caso do OSPF não é importante o ponto de captura
pois todas as informações são enviadas para todos
através de inundação.
Medições Combinadas
69


Ao medir a infraestrutura ou descobrir características
de topologia , frequentemente é útil fundir diferentes
tipos de medições, combinando medições ativas e
passivas.
Uma dificuldade com medições ativas é a grande
quantidade de tráfego de testes que é necessária,
mesmo quando a finalidade é a de mapear um único
AS.

Usando dados do BGP é possível limitar os testes apenas
para os endereços que provavelmente fazem parte do AS
alvo.
Medições Combinadas
70



Outro modo de melhorar os mapas de AS é aumentar
passivamente topologias obtidas através do BGP com
conexões adicionais inter-AS inferidas a partir de
medições ativas (traceroute).
Da mesma forma podem se usados Registros de
Roteamento Internet para ampliar as topologias
derivadas através do BGP.
Ao estudar a dinâmica do congestionamento, é possível
correlacionar grandes conjuntos de medições de RTT
com dados de topologia derivados do BGP para
localizar degradações de desempenho na Internet.
Medições de Largura de Banda
71

Largura de banda ou vazão (throughput):


Quantidade de dados que pode ser transmitida por
unidade de tempo.
Importância:
Aplicações multimídia podem ajustar suas taxas de
transmissão
 Seleção do servidor com conexão adequada
 Estimativa do produto banda-atraso para o controle de
fluxo do TCP
 Redes overlay: identificação de “bons” caminhos
 Verificação de SLAs entre usuários e provedores de rede

Medições de Largura de Banda
72


Geralmente é um processo ativo, no qual pacotes são
injetados na rede e o processo de medição é baseado na
observação dos resultados.
Algumas vezes assume-se que:



ambos os lados do caminho de medição estejam instrumentados,
enquanto que
outras vezes assume-se que um dos lados esteja instrumentado e
o outro simplesmente deve responder a um pedido de eco ICMP
ou algo semelhante.
Foram propostos também métodos passivos e as aplicações
podem usar os seus próprios pacotes de dados como fonte
de informação para a estimativa de largura de banda.
Medições de Largura de Banda
73

Link gargalo: é aquele que possui a menor vazão
durante o período de medição.
 Em
alguns casos basta medir a largura de banda do
link gargalo. Enquanto que em outros casos deseja-se
obter a largura de banda de cada um dos links.

Nos casos em que uma única etapa do IP
corresponder a uma sequência de múltiplos links
físicos pode ser um desafio inferir a largura de
banda de cada link.
Tipos de Largura de Banda
74



Capacidade
Banda disponível
Capacidade de transferência em lote (bulk)
Capacidade
75



Vazão máxima que um enlace ou caminho pode
suportar.
Algumas vezes é chamada de largura de banda
‘sem congestionamento’
A capacidade é uma propriedade de um caminho
que não muda frequentemente.
 Muda
apenas quando a infraestrutura subjacente
(roteador e/ou velocidade dos links) muda.
Banda disponível
76



Porção da capacidade que não está em uso
durante um certo intervalo de tempo.
Também chamada de capacidade residual.
Por exemplo:
 Se
um link possui uma capacidade de 1000 Mbps e
atualmente está fluindo 600Mbps através do link,
então a banda disponível é de 400Mbps.
Banda Disponível
77


A utilização média durante o período (𝑡 − 𝜏, 𝑡] é definida
como a fração de tempo durante aquele intervalo no qual
a interface está ocupada transmitindo dados.
Ou seja, se 𝑢 𝑡 ∈ 0,1 denotar a atividade instantânea
do link no instante 𝑡 (𝑢 𝑡 = 1 iff a interface estiver
ocupada), então a utilização média do link associado é
definida como


𝑢 𝑡 − 𝜏, 𝑡 =
1 𝑡
𝑢
𝜏 𝑡−𝜏
𝑥 𝑑𝑥
A largura de banda disponível de uma etapa com
capacidade 𝐶 para o dado intervalo de tempo seria então:

1 − 𝑢 𝑡 − 𝜏, 𝑡 𝐶.
Capacidade de transferência em lotes
(bulk)
78


A banda disponível não é necessariamente o que seria
obtido por uma nova conexão fazendo uso do link ou
caminho.
Muitas transferências de dados na Internet fazem uso do
TCP para controle de fluxo e os algoritmos de controle do
TCP interagirão com o tráfego competidor de uma maneira
complexa.


Por exemplo, se a banda disponível num dado caminho for de
400Mbps, uma nova conexão fluindo por aquele caminho pode
fluir a 400Mbps, 500Mbps ou até 300Mbps.
Taxa que seria obtida por uma nova conexão TCP que
perdure por algum tempo naquele dado caminho.

Esta definição assume que a taxa da conexão está limitada
apenas pela sua janela de congestionamento e não por outros
fatores.
Métodos de Medição de Largura de
Banda
79


Baseados em observar como o atraso dos pacotes
são afetados pelas propriedades do enlace.
Atraso de enfileiramento
 Efeito
depende do tamanho dos pacotes que estão
enfileirados na sua frente
 Base para os métodos de pares de pacotes

Atraso de transmissão
 Depende
apenas do tamanho do próprio pacote
 Base para os métodos de tamanho-atraso.
Métodos de Pares de Pacotes
80

Medição de Capacidade




Pacotes de mesmo comprimento estão sendo transmitidos da
esquerda para a direita e enfileiram no link mais estreito.
A capacidade mais baixa do link estreito impõe um atraso fixo
entre a borda inicial de dois pacotes sucessivos, relacionado ao
comprimento fixo do pacote.
Este atraso fixo é preservado quando os pacotes deixam este
link mais estreito.
Este atraso pode então ser medido e serve para inferir a largura
de banda do link mais estreito.
Métodos de
Pares de Pacotes
81



Para um dado par de pacotes, definimos a diferença
entre pacotes Δ𝑖 como o tempo desde que a borda
inicial do primeiro pacote chega ao link 𝑖 e a borda
inicial do segundo pacote chega ao mesmo ponto.
No caso mostrado na figura não há pacotes
entremeados com os dois que formam o par de
pacotes.
Neste caso, se o primeiro pacote tiver comprimento 𝐿 e
a capacidade do link 𝑖 for C𝑖 , então:

Δ𝑖+1 = max Δ𝑖 ,
𝐿
𝐶𝑖
.
Métodos de
Pares de Pacotes
82




Note que para que isto ocorra os pacotes de teste devem
estar enfileirados um após o outro no link mais estreito.
Se a capacidade do link estreito for 𝐶 e o intervalo entre
pacotes na origem for Δ0 , então, uma forma de tornar
provável o enfileiramento no link mais estreito é enviar
pacotes de teste com Δ0 < 𝐿/𝐶.
O princípio básico para estimar capacidade por este
método é enviar pares de pacotes por um caminho de rede
formado por 𝐻 links.
Então, se nenhum outro pacote estiver fluindo por nenhum
dos links neste caminho, e se os pacotes de teste
enfileirarem por serviço no link mais estreito,

Δ𝐻+1 =
𝐿
max Δ𝑖 ,
𝐶𝑖
𝑖∈0,…,𝐻
=
𝐿
min 𝐶𝑖
𝑖∈0,…,𝐻
=
𝐿
.
𝐶
Métodos de Pares de Pacotes
83

Dificuldades:
É
preciso garantir que os pacotes enfileirem no
gargalo: a taxa de envio deve ser maior do que a
capacidade do enlace gargalo
 Efeito de tráfego cruzado:
 Pacotes
individuais do par podem experimentar diferentes
atrasos de enfileiramento ao longo do caminho.
 Este efeito pode ser difícil de prever.
 Uma variação no tráfego cruzado pode causar que um
determinado par de pacotes relatem uma estimativa de
banda maior ou menor do que o valor real.
Métodos de Pares de Pacotes
84

Largura de banda disponível

Assume:
Enfileiramento FIFO
 Fila do roteador não esvazia entre as chegadas do primeiro e do
segundo pacote de teste
 Assume que o enlace mais ocupado é também o mais estreito.
 E que o intervalo final Δ𝐻+1 , que é o que pode ser medido, é o
mesmo que o intervalo estabelecido pelo link mais estreito Δ𝑖+1

Métodos de Pares de Pacotes
85

Largura de banda disponível
 Se
estas hipóteses forem verdadeiras então a largura
de banda disponível pode ser estimada como:
𝐴
=𝐶× 1−
 Estas
Δ𝐻+1 −Δ0
Δ0
.
hipóteses impõem uma alta carga no enlace
gargalo.
Método de Comprimento-Atraso
86


Na ausência de tráfego cruzado, o atraso
experimentado por um pacote que passa através
de um enlace é afetado pelo comprimento do
pacote e pela capacidade do enlace.
Variando o comprimento do pacote pode-se
observar o efeito do atraso e inferir a capacidade
do enlace.
Método de Comprimento-Atraso
87

A cada etapa, os atrasos principais experimentados por um
pacote de teste são:






Atraso de enfileiramento
Atraso de transmissão e
Atraso de propagação.
O atraso de propagação é determinado pelo comprimento
do link e a velocidade de propagação do sinal e é,
portanto, independente do tamanho do pacote.
Da mesma forma, o atraso de enfileiramento é determinado
pelos pacotes que estão na frente dos pacotes de teste e
não é determinado pelas propriedades do pacote em si.
Apenas o atraso de transmissão é afetado pela
capacidade do link e o tamanho do pacote de testes.
Método de Comprimento-Atraso
88


Portanto, se não houver tráfego cruzado, podemos
expressar o atraso de um pacote de comprimento 𝐿
após ter passado por 𝑖 etapas, como:
𝐿
𝑖
𝑘=1 𝐶

𝑇𝑖 𝐿 = 𝛼𝑖 +

Onde 𝛼𝑖 consiste nos atrasos até a etapa 𝑖 que não
dependem de 𝐿.
𝑘
= 𝛼𝑖 + 𝛽𝑖 𝐿
A última igualdade mostra que podemos capturar
todas as capacidades até a etapa i com um único
termo:
1
𝑖
𝑘=1 𝐶 .

𝛽𝑖 =

O relacionamento entre 𝛽𝑖 e 𝐿 é o que pode ser medido.
𝑘
Método de Comprimento-Atraso
89


A abordagem geral é enviar um certo número de pacotes
com comprimento variável 𝐿, e estimar os valores de 𝛼𝑖 e 𝛽𝑖
a partir dos resultados medidos, por exemplo através de
regressão linear.
Assim, a capacidade em cada etapa pode ser estimada
Vantagem em
como:


𝐶𝑖 =
1
,
𝛽𝑖 −𝛽𝑖−1
com 𝛽0 = 0.
Relação aos
Pares de Pacotes
Implementar este método na prática requer medir o tempo
de propagação dos pacotes de teste.


Na ausência de instrumentação, usam-se pacotes com limites no
TTL para provocar respostas ICMP TIME EXCEEDED.
Na ausência de tráfego cruzado o tempo gasto para receber
esta mensagem ICMP é capturada pelo termo 𝛼𝑖 dado que as
respostas têm todas o mesmo tamanho.
Problemas com o Método de
Comprimento-Atraso
90

Uma complicação considerável é a necessidade de
que os pacotes de teste passem pela rede sem
enfileirar atrás de tráfego cruzado.
 Este
problema é geralmente enfrentado enviando
muitos pacotes de teste para cada etapa que está
sendo medida, e observando o menor tempo de
propagação obtido para cada etapa.
 Com o crescimento do comprimento do caminho, esta
hipótese fica mais suspeita, dado que fica mais difícil
para um pacote passar por muitas etapas sem
experimentar fila em nenhuma delas.
Problemas com o Método de
Comprimento-Atraso
91

Outra preocupação é que com o crescimento do
comprimento do caminho, fica mais difícil de medir
a quantidade 1/(𝛽𝑖 − 𝛽𝑖−1 ) com precisão.
O
fato de que os pacotes possuem uma faixa limitada
de valores limita a precisão de uma estimativa de 𝛽𝑖 .
 Com o crescimento de 𝑖, as diferenças entre valores
sucessivos de 𝛽𝑖 são cada vez menores, e pequenos
erros na estimativa de 𝛽𝑖 se traduzem em grandes
erros na estimativa de 𝐶𝑖 .

É, portanto, difícil usar este método para medir
caminhos longos.
Problemas com o Método de
Comprimento-Atraso
92

Este método assume que o comprimento do pacote
não varia ao atravessar um caminho.
 Isto
nem sempre é verdade: os cabeçalhos de camada
2 podem comprimentos diferentes em etapas distintas.
 A extensão da imprecisão introduzida depende do
tamanho do pacote: os erros serão maiores para
pacotes menores.
Combinação dos Métodos “Pares de
Pacotes” e “Comprimento-Atraso”
93



Uma ideia é enviar pares de pacotes de comprimentos
variáveis.
Quando um par de pacotes consiste em um pacote
grande seguido por um ou mais pacotes pequenos, é
mais provável que o pacote maior enfileire em um
dado link.
Se o pacote maior tiver um TTL limitado ele será
descartado no link a ser medido, enquanto que o
demais pacotes prosseguirão até o destino levando
informação sobre o atraso experimentado pelo pacote
maior até o link em que foi descartado.
Congestionamento autoinduzido
94



Objetivo: Encontrar a taxa mínima dos pacotes de teste que criam
congestionamento (enfileiramento) no caminho.
Usado normalmente para se obter a capacidade disponível
Ideia básica:





Enviar pacotes numa taxa 𝑅 e notar se aparentemente estão sendo
formadas filas ao longo do caminho que está sendo medido.
Assume-se que a formação da fila está ocorrendo no link gargalo.
Mas, se a taxa 𝑅 for menor do que a capacidade disponível no link
gargalo o atraso em um sentido não deverá crescer em média.
O comprimento usado do trem de pacotes determina a escala de tempo
na qual os pacotes de teste interagem com o tráfego cruzado no
caminho.
Este método dá uma resposta booleana para cada taxa 𝑅.
Portanto, para se encontrar eficientemente a verdadeira
capacidade disponível deve-se adotar uma estratégia de busca
binária ou uma taxa com crescimento exponencial.
Dificuldades dos Métodos de
Congestionamento autoinduzido
95

Devido à explosividade (burstiness) do tráfego possui
uma tendência em subestimar a banda disponível.



Esta tendência diminui à medida que o comprimento do
trem de pacotes aumenta.
O pacote de teste é, por definição, grande o bastante
para afetar o tráfego cruzado e pode, portanto,
mudar a própria quantidade que está sendo medida.
Assume-se que a formação de fila ocorre em um único
link. A presença de múltiplos links com
aproximadamente a mesma largura de banda
disponível causará uma subestimação.
Dificuldades dos Métodos de
Congestionamento autoinduzido
96


Assume-se que o tráfego cruzado varie lentamente
o suficiente que a quantidade que está sendo
medida esteja estável o suficiente para que o
método convirja.
Finalmente, estes métodos assumem um
enfileiramento FIFO em todos os roteadores, o que
nem sempre é verdade na Internet atual.
Medição da Capacidade de
Transferência em Lote
97

Abre uma conexão TCP e envia tantos dados
quanto o caminho possa suportar.
 Apesar
de ser um método intrusivo, ele é mais simples e
mais robusto do que a maioria dos outros métodos de
estimativa de largura de banda.

Requer cooperação das duas extremidades, requer
a instalação de software (ex.: iperf).
Medição da Capacidade de
Transferência em Lote
98

Fatores que influenciam a vazão TCP e que devem
ser consideradas:
 Tamanho
da transferência: É necessária uma
transferência longa (dezenas de segundos)
 Natureza do tráfego cruzado: TCP x UDP; muitas x
uma conexão TCP
 Comprimento dos buffers nos dois lados.
 Variações na especificação e implementação da
variante do TCP utilizada.
Desafios na Medição de Largura de
Banda
99



Nos enlaces de alta capacidade os atrasos são tão
pequenos que é muito difícil ou impossível de serem
medidos com precisão.
Enlaces sem fio: muda a taxa e não entrega de
acordo com FIFO.
Atrasos adicionais de dispositivos de nível 2 (ex.:
switches)
Medição e Estimação de Latência
100


Além da medição de largura de banda, um segundo
problema importante é a medição ou a estimação da
latência ao longo de caminhos da Internet.
Importância em:
Redes de distribuição de conteúdo: fornecer objetos Web
ao cliente a partir da réplica disponível mais próxima.
 Redes P2P: recuperação de objetos a partir de pares
próximos.
 Jogos multiusuários: busca por jogadores que estejam
próximos.
 Seleção de servidores dinâmicos: fornecer objetos Web
ao cliente a partir do servidor mais próximo que possua
uma réplica dos mesmos.

Latência da Rede
101




Uma indicador do desempenho que o caminho de
rede envolvido pode suportar.
RTT mínimo (minRTT): Interesse pois muda em escala
de tempos longa, i.e., apenas com a mudança da
topologia ou do roteamento.
RTT instantâneo: Varia dinamicamente de acordo
com o congestionamento
Pode também ser medido em um único sentido.
Estimação da Latência
102


Se um dos lados do caminho puder ser
instrumentado, a medição da latência é direta
(usando ping).
Desafios (medição de atraso sem o envio de
pacotes de teste entre eles):
 Métodos
baseados em proxy: quando nenhum dos dois
pontos terminais de um caminho pode participar do
processo de medição.
 Métodos de incorporação: os hosts são capazes de
efetuar medições, mas não se quer medir cada caminho
de interesse diretamente.
Elementos
103

Todos os métodos para estimativa da latência
contam com alguns nós fixos que agem como:
 intermediários
(proxies) ou como
 pontos de referência (landmarks).
Desigualdade Triangular
104

Dados três pontos: 𝑥, 𝑦 e 𝑧 e uma função 𝑑(⋅,⋅) que denota
a distância entre dois pontos, a desigualdade triangular
requer que:



𝑑 𝑥, 𝑦 + 𝑑 𝑦, 𝑧 ≥ 𝑑 𝑥, 𝑧
Esta propriedade se verifica para medidas de distância em
espaços métricos (como o espaço Euclidiano).
Quando os pontos são nós de rede e a função distância é a
latência da rede, a desigualdade triangular nem sempre se
verifica:


As medidas instantâneas variam muito com o tempo e é difícil
medi-las no mesmo instante de tempo.
Mesmo para minRTT em alguns casos os pacotes enviados de 𝑥
para 𝑧 podem não ser capazes de usar as rotas de 𝑥 para 𝑦 e
de 𝑦 para 𝑧. Por exemplo, por causa de políticas de roteamento
inter-AS.
Métodos baseados em proxy
105


Tem como objetivo do RTT atual entre dois nós.
Um método simples pode ser formulado baseado na
hipótese de roteamento pelo caminho mais curto e, portanto,
na validade da desigualdade triangular.


Um conjunto de proxies {ℓ𝑖 } é selecionado.
Para dois nós 𝑛1 e 𝑛2 , a desigualdade triangular requer que
𝑑(𝑛1 , 𝑛2 ) seja limitado por baixo por
𝐿 = max 𝑑 𝑛1 , ℓ𝑖 − 𝑑 𝑛2 , ℓ𝑖
𝑖

E limitado por cima por
𝑈 = min 𝑑 𝑛1 , ℓ𝑖 + 𝑑 𝑛2 , ℓ𝑖
𝑖

Médias ponderadas de 𝐿 e 𝑈 podem ser usados como
estimativas de 𝑑(𝑛1 , 𝑛2 ). Infelizmente elas são bem grosseiras
dependendo da localização dos proxies.
Métodos baseados em proxy
106

IDMaps:





Faz uso de uma infraestrutura de medição especialmente
instalada.
Assume a disponibilidade de proxies particulares chamados de
tracers.
A latência entre os nós 𝑛1 e 𝑛2 é estimada como a latência entre
𝑛1 e o tracer mais próximo dele, mais a lantência entre 𝑛2 e o
tracer mais próximo dele, mais a latência medida entre estes dois
tracers.
O sistema também usa uma coleção de servidores que
respondem a consultas dos clientes e retorna a estimativa da
latência na rede.
A acurácia do IDMaps é limitada quando um ou os dois nós estão
distantes dos tracers mais próximos.
Métodos baseados em proxy
107

King:
 Aborda
algumas das desvantagens do IDMaps
explorando o sistema DNS
 Ao invés de contar com tracers instalados especialmente
para esta finalidade, ele usa o servidor DNS local de
um nó como o seu proxy de medição.
Métodos baseados em proxy
108

King:

O método é baseado nas seguintes observações:
Muitos nós na Internet estão próximos de seus servidores locais
DNS.
 É possível disparar trocas entre servidores DNS arbitrários usando
consultas DNS recursivas.



Dados dois servidores de nomes em domínios diferentes (ex.,
dns.first.com e dns.second.com), uma consulta recursiva
a dns.first.com para um nome como any.second.com irá
disparar uma consulta DNS de dns.first.com para
dns.second.com.
Ele mede o tempo de uma consulta recursiva do
dns.first.com para any.second.com para estimar a
latência entre um host no domínio first.com e um host no
domínio second.com.
Métodos de Incorporação
109




A abordagem da incorporação está geralmente
focada em estimar o minRTT.
Nesta abordagem, atribui-se a cada nó uma
localização em um espaço Euclidiano abstrato de alta
dimensionalidade ℝ𝑟 .
A localização de um nó neste espaço pode ser fixada
usando um conjunto de medições para landmarks.
Apenas as landmarks precisam realizar medições de
latência entre cada par delas, e não é necessário um
grande número de landmarks para se obter estimativas
acuradas.
Métodos de Incorporação: GNP
110


Na inicialização as 𝑁 landmarks
ℓ1 , ℓ2 , … , ℓ𝑁 efetuam medições de latência entre
todos os pares fornecendo um conjunto de medições
𝑑 ℓ𝑖 , ℓ𝑗 .
É atribuído então a cada landmark ℓ𝑖 um vetor de
coordenadas 𝑥𝑖 ∈ ℝ𝑟 . Esta atribuição é obtida
pela minimização da função objetivo:
 𝑓ℓ
𝑥1 , … , 𝑥𝑁 =
 onde
𝑖,𝑗∈1,…,𝑁 𝑒𝑟𝑟
𝑒𝑟𝑟 𝑎, 𝑏 = (𝑎 − 𝑏)2 .
𝑑 ℓ𝑖 , ℓ𝑗 , 𝑥𝑖 − 𝑥𝑗
2
Métodos de Incorporação: GNP
111



Esta formulação resulta num problema de otimização não
linear cuja solução aproximada é obtida por métodos
iterativos.
A dimensão do espaço Euclidiano (𝑟) é um parâmetro
ajustável.
Cada nó 𝑛𝑖 encontra o seu próprio vetor de coordenadas
𝑥𝑖 através da minimização de uma função objetivo
semelhante:


𝑓𝑛 𝑥𝑖 =
𝑗∈1,…,𝑁 𝑒𝑟𝑟
𝑑 𝑛𝑖 , ℓ𝑗 , 𝑥𝑖 − 𝑥𝑗
2
O benefício deste procedimento é que, depois que cada nó
tiver o seu vetor de coordenadas, a latência entre os nós 𝑛𝑖
e 𝑛𝑗 pode ser estimada sem nenhuma medição adicional
por:

𝑑 𝑛𝑖 , 𝑛𝑗 ≈ 𝑥𝑖 − 𝑥𝑗
2
Métodos de Incorporação: GNP
112

Dado que a carga de medições para cada
landmark pode ser alto,
 As
landmarks podem ser divididas em conjuntos, onde
cada alvo realiza medições apenas para um destes
conjuntos.
 Como dois nós podem usar conjuntos distintos, pode-se
aplicar uma função de transformação para mapear
cada conjunto de coordenadas locais num sistema
canônico de coordenadas global.
 Pode-se também eliminar as landmarks, usando os
próprios nós para isto.
Geolocalização
113



Problema: Dado o endereço de rede de um host alvo, qual
é a localização geográfica deste host?
É importante reconhecer que muitos métodos de
geolocalização comumente usados podem ser muito
imprecisos.
Razões:




O endereço que está sendo localizado não está correto
Pode não ser possível realizar as medições necessárias para
realizar corretamente a geolocalização
Alguns métodos contam com bases de dados que mapeiam redes,
organizações ou blocos de endereços inteiros num único local.
Usuários podem usar contramedidas para não serem localizados.
Geolocalização e Privacidade
114



Os usuários podem não querer divulgar suas
localizações
Enquanto outros podem permitir a divulgação mas
restringir a precisão da mesma, além de restringir
se pode ou não ser armazenada.
O GT geopriv do IETF definiu um conjunto de
padrões para tratar informações de localização.
Geolocalização baseada em Nome
115

Abordagem simples:
 Inspecionar
os nomes DNS do host alvo, ou de hosts
próximos topologicamente ao host alvo.
 Este método se baseia na observação de que os
operadores de rede frequentemente atribuem nomes
com significado geográfico a suas interfaces.
 Quando o host alvo não é um roteador, procurando o
roteador que esteja próximo em termos da topologia
da rede pode fornecer informações úteis.
 Este método é sujeito a erros pois nem sempre os
roteadores têm nomes com significado geográfico.
Geolocalização baseada em Atrasos
116

Outra abordagem é explorar o relacionamento entre o
atraso de rede medido e a distância.



Métodos principais:




Medições do atraso mínimo em um dado caminho.
Os caminhos medidos certamente serão mais longos do que a
distância real entre os pontos terminais.
Melhor landmark
Baseado em restrições
Em ambos assume-se a existência de um conjunto de 𝑁
landmarks {ℓ𝑖 , 𝑖 = 1, … , 𝑁} com localizações geográficas
conhecidas.
Representamos o atraso mínimo entre os nós 𝑛1 e 𝑛2 como
𝑑 𝑛1 , 𝑛2 .
Geolocalização:
Método da Melhor Landmark
117


Mapeia o nó alvo à localização da landmark mais próxima.
O método inicia com a medição do atraso de rede de cada
landmark para todas as demais:


Para localizar um nó alvo 𝜏, são realizadas medidas de
latência mínima para todas as landmarks e construído o
vetor de medições correspondente


ℓ𝑖 = 𝑑 ℓ𝑖 , ℓ1 , 𝑑 ℓ𝑖 , ℓ2 , … , 𝑑(ℓ𝑖 , ℓ𝑁 )
𝜏 = 𝑑 𝜏, ℓ1 , 𝑑 𝜏, ℓ2 , … , 𝑑(𝜏, ℓ𝑁 )
Escolhe-se a melhor landmark como sendo aquela cujo vetor
de medição é mais semelhante a 𝜏:

𝑚 = arg min ℓ𝑖 − 𝜏
ℓ𝑖
2
Método da Melhor Landmark:
Limitações
118

A acurácia da localização inferida é limitada pela
distribuição espacial das landmarks.
 Se
não houver landmarks próximas ao alvo, a
localização inferida será inacurada.
Geolocalização baseada em
Restrições
119

Nesta abordagem são exploradas as propriedades
conhecidas da propagação do sinal em uma fibra
A
luz se propaga a aproximadamente 2/3 da sua
velocidade no vácuo.

Encontra-se uma estimativa da localização de um
host alvo através de multilateração
 Processo
de estimar a posição usando um número
suficiente de distâncias até pontos fixos (por exemplo,
usado por GPSs).
Multilateração
120


Para cada landmark ℓ𝑖
podemos usar 𝑑(ℓ𝑖 , 𝜏)
para obter um limite
superior na distância
até o alvo.
Cada landmark ℓ𝑖
calcula a distância
geográfica restrita a um
host alvo 𝜏 multiplicando
a latência mínima
medida pela velocidade
da luz na fibra.

A restrição na distância
geográfica calculada é
dada por:


𝑔𝑖𝜏 = 𝑔𝑖𝜏 + 𝛾𝑖𝜏
A localização do host 𝜏
está em algum lugar na
região cinza.
Banco de Dados de Localização
121


Construção manual de uma grande base de dados com
mapeamentos entre endereços IP e suas localizações
conhecidas.
Informações de localização podem ser fornecidas por
administradores de rede.


O DNS foi proposto como repositório para esta informação.
Bancos de dados do serviço whois inclui entradas de
localização para sistemas autônomos e blocos de
endereços alocados.

Estas informações podem ser imprecisas ou desatualizadas.
Inferência
122

Dados escondidos na medições de infraestrutura
podem às vezes ser reconstruídos através de
procedimentos de inferência (Tomografia de rede).
Topologia da rede
 Atrasos internos à rede
 Taxas de perdas de pacotes


Tomografia da rede baseada na equação
𝑦 = 𝐺𝑥
 Onde:

𝑦 é um conjunto de 𝑚 medições fim-a-fim
 𝐺 = 𝐴𝑇 é a matriz de roteamento 𝑚 × 𝑛 e
 𝑥 são as 𝑛 medições individuais de cada link

Atrasos Internos e Taxas de Perdas
123

Hipóteses para a estimativa:
 Links:
unidirecionais ou bidirecionais
 Caminhos: simétricos ou assimétricos
 Medições dos caminhos: ida-e-volta (RTT) ou em um
sentido (OW)
 Estratégia de testes: multicast ou unicast.

Hipóteses mais realistas:
 Links
unidirecionais e caminhos assimétricos.
Soluções
124

Em geral a equação 𝑦 = 𝐺 𝑥 pode:
ter nenhuma solução para 𝑥
 Ter uma única solução ou
 Ter um número infinito de soluções.
 Não

Se 𝐺 𝑇 𝐺 for uma matriz com posto máximo, então a
equação pode ser resolvida diretamente para
todas as medições nos links sendo a solução dada
por
𝑥
= 𝐺𝑇𝐺
−1 𝐺 𝑇 𝑦
Inferências em todos os links
125


É preciso fazer hipóteses adicionais.
Uma estratégia geral é olhar soluções de máxima
verossimilhança:

Dadas medições 𝑦 podemos definir a probabilidade de
uma solução particular 𝑙(𝐺, 𝑥) como:
𝑙 𝐺, 𝑥 = p(𝑦|G, 𝑥)
 Onde p(𝑦|G, 𝑥) é a probabilidade de ver as observações 𝑦
dada uma matriz de roteamento particular e um conjunto de
parâmetros de link.
 As hipóteses adicionais que são incluídas tomam a forma de
modelos ou restrições que afetam como calculamos p(𝑦|G, 𝑥)

Tomografia de rede:
Métodos baseados em Multicast
126


Abordagem MINC baseada
no uso de testes em multicast.
Problema de tomografia na
sua forma mais simples:




Cada um dos links possui uma
taxa de perdas associada 𝛽𝑖 .
O objetivo é estimar as três
taxas de perda a partir de
medições de taxa de perdas
realizadas apenas nos
caminhos 0 → 2 e 0 → 3.
Como temos três links e
apenas duas medições, o
problema é indeterminado
(múltiplas soluções estão
consistentes com os dados
observados).
Na abordagem MINC, ao
invés de trabalhar com taxas
de perdas trabalharemos com
eventos de perdas.
Tomografia de rede:
Métodos baseados em Multicast
127


A fonte dos testes (nó 0) envia pacotes multicast em em
em direção aos nós terminais (nós 2 e 3).
Quando os pacotes multicast alcançam o ponto de
bifurcação 1, uma cópia do pacote é enviada por
cada um dos links 1 → 2 e 1 → 3.
Se o pacote se perder no link 0 → 1 não chegará nem ao
nó 2 nem ao nó 3. Portanto, os pacotes que não chegarem
nem a 2 nem a 3 devem ter se perdido no link 0 → 1.
 Os pacotes que forem vistos em um nó mas não no outro,
devem ter se perdido no link que leva ao nó onde ele não
chegou.
 Repetindo este experimento diversas vezes podemos
construir uma estimativa das taxas de perdas nos três links.

Tomografia de rede:
Métodos baseados em Unicast
128




Algumas redes não suportam multicast.
Ao usar unicast tentaremos imitar o ‘destino
compartilhado’ dos pacotes de teste multicast.
Para este fim podemos usar pares de pacotes dado
que eles tendem a sofrer as mesmas consequências
de enfileiramento e perda.
Métodos unicast são mais imprecisos que os
multicast, mas são mais flexíveis.
 Por
exemplo, podem ser estendidos a medições
passivas.
Tomografia de Rede:
Links Congestionados Dominantes
129

Em alguns casos pode haver um link ao longo do caminho
que seja responsável pela maioria das perdas ou atrasos,
que é chamado de link congestionado dominante.



Pode ser suficiente determinar se existe um link congestionado
dominante e
Em caso afirmativo, identificar este link
Uma abordagem é enviar pacotes periódicos ao longo do
caminho e observar a sequência de valores de atrasos.


O atraso sofrido pelo pacote perdido pode ser inferido pelos
atrasos dos pacotes não perdidos.
Se a maior parte dos pacotes perdidos tiver atrasos inferidos
semelhantes pode ser inferido que existe um link congestionado
no caminho.
Tomografia de Rede:
Links Congestionados Dominantes
130

A identificação do link congestionado pode ser
feita (assumindo que a incidência dos mesmos seja
baixa) através da interseção de desempenho ruim
entre caminhos diversos.
Projetos Eficientes de Medição
131




Um papel relacionado para a inferência é na
redução da carga requerida para a obtenção das
medições de rede.
Realizar medições em 𝑘 caminhos linearmente
independentes de modo que possam descrever
completamente todos os 𝑂 𝑚2 caminhos.
Da mesma forma, se quisermos monitorar a falha
de links podemos encontrar o número mínimo de
caminhos a serem monitorados.
Estimação estatística (resultados aproximados)
Outras ferramentas
132

Identificação da Topologia:
 Árvores

Taxa de reordenação de pacotes:


multicast
observando as propriedades de conexões TCP
Taxas de perdas de pacotes em um sentido
 Envio
de pacotes TCP selecionados e deduzir a
quantidade de pacotes perdidos em cada direção em
função das respostas do host remoto.
133
Estado da Arte
Roteiro
134



Propriedades dos Equipamentos
Propriedades das Topologias
Interação do Tráfego com a Rede
Propriedades dos Equipamentos:
Roteadores
135

Através de avaliações experimentais dos
roteadores de backbone mostraram que o atraso
experimentado por um pacote quando passa por
um roteador é muito pequeno:
≥
20 microssegundos: quando o pacote chega e sai da
mesma interface com pouco tráfego adicional na
mesma.
 Dezenas de microssegundos: quando o pacote entra e
sai por interfaces distintas.
Propriedades dos Equipamentos:
Roteadores
136



No entanto, se o roteador estiver bem carregado, os atrasos
de enfileiramento podem ser da ordem de dezenas de
milissegundos.
Uma outra fonte de atrasos (que pode estar na faixa dos
milissegundos) ocorre quando o pacote contém opções IP.
Em algumas raras ocasiões o roteador atrasa a transmissão
de pacotes mesmo na ausência de tráfego esperando para
ser transmitido no link de saída (isto afeta menos de 1% do
tráfego).


Estes atrasos são da ordem de milissegundos e
Parecem ocorrer com a ativação periódica de software no
roteador.
Propriedades dos Equipamentos:
Roteadores
137

É útil também entender como os roteadores produzem e
consomem tráfego


por exemplo, mensagens de roteamento.
Mensagens de anúncio do estado de enlaces (LSAs)
requerem da ordem de 100 microssegundos para serem
processadas.



Boa parte disto pode ser atribuída à cópia de dados dentro do
roteador.
O tempo necessário para processar os pacotes OSPF tende a
variar linearmente com o número de LSAs contidos no pacote
Enquanto que o tempo associado ao cálculo do caminho mais
curto cresce de forma quadrática em relação ao número de nós.
Propriedades dos Equipamentos:
Middleboxes
138


Caixas intermediárias tais como NATs e firewalls.
Estes dispositivos podem introduzir atrasos de um
milissegundo a centenas de milissegundos para
encaminhar os pacotes.
Propriedades das Topologias
139

Propriedades estáticas do Grafo de Sistemas
Autônomos:

Alta variabilidade da distribuição de graus:
Grafos aleatórios tradicionais apresentam baixa variabilidade
na distribuição dos graus.
 Mas este não é o caso para o grafo de ASes.

𝑦 = 𝑎𝑥 𝑘 + 𝜀
Propriedades das Topologias
140

Alta variabilidade da distribuição de graus:

Consequências:



Esta é uma invariante importante que deve estar presente em
qualquer modelo realista de topologia de ASes.
Alguns ASes são muito bem conectados, enquanto que outros são
muito pouco conectados. Papeis muito diferentes: grau do nó parece
estar altamente correlacionado com o tamanho do AS.
Mecanismos de crescimento da Internet:
 Nós adicionais se conectam com nós existentes com uma
probabilidade proporcional ao grau do nó existente.
 Nós adicionais conectam a nós existentes de modo a minimizar
tanto o comprimento físico da nova conexão como o número
médio de etapas para outros nós na rede
 Se novos ASes surgirem com uma taxa de crescimento
exponencial e cada AS também crescer exponencialmente. Se
o tamanho do AS estiver correlacionado com o seu grau então
obteremos distribuições de graus altamente variáveis.
Propriedades das Topologias
141
 Propriedades
de Mundo Pequeno:
 Diz
respeito ao relacionamento de duas propriedades dos
grafos: diâmetro e agrupamento (clustering):

Normalmente têm um alto grau de agrupamento e pequenos
diâmetros!
 Grafos

de ASes são grafos de mundo pequeno:
Dados de Janeiro 2002 continham 12.709 ASes e 27.384
arestas. Comprimento médio do caminho é de 3,6 e o coeficiente
de agrupamento é 0,46 (grafos aleatórios semelhantes
apresentam um coeficiente de 0,0014).
Propriedades das Topologias
142

Relacionamentos entre ASes:
Os ASes podem ser identificados de acordo com os papeis que
desempenham na rede.
 O relacionamento comercial entre dois ASes pode ser classificado
como:






Cliente-provedor
Parceiros
Trânsito mútuo
Backup mútuo
Estes relacionamentos são aplicados através da escolha de que
rotas são anunciadas através do BGP, e para quem elas são
anunciadas.

Portanto, pode ser difícil identificar a natureza dos relacionamentos
sem o acesso direto ao tráfego BGP entre os ASes de interesse.
Propriedades das Topologias
143

Propriedades estáticas dos Grafos de Roteadores:
 Grafo
de roteadores: grafo no qual os nós são os
roteadores e as arestas são conexões diretas (1 etapa)
entre roteadores.
 Obter uma visão completa do grafo de roteadores da
Internet hoje é impossível.
É
mais fácil focar em pequenos pedaços, ou seja, subgrafos
correspondentes a um único AS ou rede.
Mapa da ARPANET em 30/12/1972
144
Mapa da Rede Abilene em 2005
145
Mapa da Rede Ipê em Maio 2011
146
Propriedades das Topologias
147

Propriedades estáticas dos Grafos de Roteadores:
 Alta
Variabilidade na Distribuição dos Graus:
 Como
os grafos de ASes, medições dos grafos de
roteadores mostraram que eles também apresentam uma
alta variabilidade na distribuição dos graus.

 Ao
Muitos nós têm graus menores do que 5 mas alguns têm graus
maiores do que 100 (provavelmente em pontos de acesso na
borda da rede).
contrário da medição de grafos de ASes que são
passivas (a partir do BGP), as medições de grafos de
roteadores são ativas (com o uso do traceroute).
Propriedades das Topologias
148

Propriedades estáticas dos Grafos de Roteadores:
 Alta
Variabilidade na Distribuição dos Graus:
 Grafo
sintético respeitando as restrições técnicas para os
roteadores:
Propriedades das Topologias
149

Propriedades estáticas dos Grafos de Roteadores:
 Propriedades
dos Caminhos:
 Como
no caso dos grafos de ASes, os caminhos típicos
através dos grafos de roteadores tendem a ser curtos
 Medidas do número de etapas IP entre nós na Internet
mostram valores médios em torno de 16, enquanto que
caminhos com mais de 30 etapas são raros.


Apesar de serem curtos, as medições têm mostrado que eles são
mais longos do que necessário.
Este efeito parece ser devido principalmente a políticas de
peering entre ASes e roteamento interdomínio.
Propriedades das Topologias
150

Aspectos Dinâmicos da Topologia:


Também temos interesse em observar como a infraestrutura da Internet
muda com o tempo.
Crescimento e mudança:
Fonte: bgp.potaroo.net
Propriedades das Topologias
151

Aspectos Dinâmicos da Topologia:

Crescimento e mudança:


Observar o crescimento da Internet ao nível dos roteadores ou dos sistemas
finais é mais complicado e muito mais dinâmico.
Alternativas:




Contar o número de endereços que foram alocados pelos Registros Regionais.
 Este seria um superdimensionamento pois é conhecido que muitos endereços
alocados não estão em uso.
Contar o número de endereços anunciados pelo BGP.
 Mesmo assim muitos endereços anunciados não estão em uso.
Testar todos os endereços anunciados usando o ping
 Mas, muitos hosts estão conectados de forma intermitente ou estão atrás de
NATs ou firewalls que bloqueiam as respostas e produzem um número
subestimado.
Consulta ao DNS para encontrar o conjunto de todos os endereços IP que
possuem nomes DNS alocados.
 Mas este seria também um valor subestimado dado que nem todos os hosts
estão cadastrados no DNS.
Propriedades das Topologias
152

Aspectos Dinâmicos da Topologia:
 Crescimento
e mudança:
Evolução do Número de Hosts do Brasil
153
Número de Hosts
Posição Relativa
Fonte: www.cetic.br
Propriedades das Topologias
154

Aspectos Dinâmicos da Topologia:
 Estabilidade:
 Mudanças
na topologia da rede podem resultar da
instabilidade do sistema.
 Os componentes da infraestrutura da rede estão
continuamente sujeitas a falhas, reinicializações e
reconfigurações.


Isto provoca alterações na topologia com nós e arestas
desaparecendo e depois reaparecendo.
Reflete também na instabilidade das rotas.
Propriedades das Topologias
155

Aspectos Dinâmicos da Topologia:
 Estabilidade:
 Instabilidade



no BGP:
Provocam sequências longas de atualizações.
Podem causar loops de roteamento e um crescimento no atraso e
perdas de pacotes.
Aparentemente afeta uma pequena parte do tráfego da
Internet.
 Num
backbone a maioria das falhas dos links está
concentrada num pequeno subconjunto dos mesmos.

E duram menos do que 10 minutos.
Propriedades das Topologias
156

Localização Geográfica:
Interação do Tráfego com a Rede
157


Muitas propriedades importantes do tráfego são
influenciadas pelas condições da rede.
Atraso dos Pacotes:

Determinísticos:

Atrasos de transmissão e propagação



O atraso de transmissão é significativo apenas em links lentos.
O atraso de propagação é influenciado pela distância geográfica.
Estocásticos:

Atraso de encaminhamento (sobretudo de enfileiramento)


Boa parte do atraso total observado é devido a este atraso.
São normalmente observados grandes picos de atraso.
Interação do Tráfego com a Rede
158

Perdas de Pacotes:
 Normalmente
ocorrem em rajadas (bursts)
provavelmente por eventos de congestionamento
persistente nos roteadores.
 Medições sugerem que as taxas de perdas em
caminhos ‘cabeados’ são, em geral, inferiores a 0,1%
 Por outro lado, taxas de perdas em caminhos que
incluem links sem fio podem ser bem altos – 2% ou
mais.
Interação do Tráfego com a Rede
159

Reordenamento de Pacotes, Duplicação e Jitter:

Causas do reordenamento dos pacotes:
Paralelismo em um roteador
 Balanceamento de carga entre múltiplos caminhos na rede
 Mudanças de rotas

O reordenamento dos pacotes têm um efeito importante no
comportamento do TCP.
 No TCP os pacotes podem chegar fora de ordem por
diversos motivos:

Reordenamento real dentro da rede
 Duplicação de pacotes dentro da rede
 Retransmissão pelo transmissor TCP (maior parte)

Interação do Tráfego com a Rede
160

Largura de Banda e Vazão:
 Há
poucos dados sobre a distribuição de larguras de
banda entre caminhos na Internet.
 As velocidades dos links estão crescendo firmemente e
continuamente.
 Portanto,
a medição de taxas em lotes tem crescido em
certos caminhos.
Lei da Largura de Banda de Edholm
161
10 Gb/s
Ethernet
Fonte: IEEE Spectrum July 2004
Interação do Tráfego com a Rede
162

Largura de Banda e Vazão:
 Em
escalas de tempo menores, a vazão em caminhos
individuais é uma métrica relativamente firme.
 Ao
contrário do RTT e taxas de perdas, as taxas de vazão
do TCP variam lentamente.
 As
taxas de vazão podem variar por um fator menor
do que três durante uma hora.
 Isto
é importante para medições de largura de banda
disponível e indica que estas medições são úteis por pelo
menos um período da ordem de horas.