Este trabalho
apresentará uma nova proposta a respeito do uso da
localização geográfica em protocolos
de roteamento. Até o momento (2007), encontramos propostas
basicamente ligadas a redes Ad-Hoc. No entanto, novas abordagens
têm surgido para tentar trazer a
informação geográfica para a internet.
Vamos concentrar o esforço especialmente em uma delas:
"GIRO" - Geographically Informed Inter-Domain Routing (Ricardo
Oliveira, Mohit Lad, Beichuan Zhang, Lixia Zhang).
Esta proposta - "GIRO" - foi apresentada na ICNP deste ano (2007) -
15th IEEE International Conference on Network Protocols
October 16-19, 2007
The Westin Beijing, Financial Street, Beijing, CHINA
No atual protocolo de
roteamento global (BGP), a escolha da rota a ser seguida é
baseada em políticas de roteamento que refletem os
interesses econômicos dos provedores de serviços
de internet (ISPs). Por exemplo, se tivermos várias rotas
que levam a uma mesma rede destino, geralmente será usada
aquela que passa por clientes do provedor de serviços. Como
sabemos, a internet possui uma topologia extremamente conectada. Com
isso, sobram muitas possibilidades de rotas mesmo passando por essas
políticas de roteamento. Quando temos uma
situação em que a escolha entre as
opções rotas parece ser indiferente, o ideal
seria que um roteador escolhesse o caminho que fosse mais curto. No
entanto, no sistema atual de roteamento, não temos
informações sobre a
localização geográfica do destino ou
sobre as distâncias percorridas pelas diferentes rotas. De
fato, estudos anteriores mostram que os caminhos utilizados
são significativamente maiores do que poderiam ser se
tivéssemos informações
geográficas.
GIRO é diferente das propostas
anteriores relacionadas à localização
geográfica porque usa a localização
para auxiliar, e não para substituir, o atual sistema
utilizado. É observado que, ao colocarmos a
informação geográfica na estrutura do
endereço IP, temos um ganho significante na escalabilidade e
no desempenho no sistema de roteamento global.
Com o uso da informação geográfica,
é possível escolher, dentre as rotas
possíveis, aquela que for mais curta. Em
simulações, foi observado que é
possível reduzir em até 30% a distância
das atuais rotas BGP. Além disso, para aproximadamente 20%
das rotas temos uma redução de até 40%
da distância. Por fim, vemos que é
possível a organização de rotas de
acordo com a localização e uma
combinação de agregações
por localização geográfica e por
topologia pode reduzir em até 75% o tamanho da tabela de
roteamento do BGP.
Como foi dito
anteriormente, existem políticas seguidas para a escolha de
rotas e, mesmo assim, temos uma variedade de
opções extensa. Quando temos essa
situação em que as políticas
são aplicadas e é possível escolher
entre diferentes rotas, o BGP decide pela que oferece o menor
número de saltos entre sistemas autônomos (ASes -
AS: Autonomous System Number).
Na figura 1, vemos um exemplo que acontece atualmente com o BGP. Para chegarmos ao AS577 em Seatle, WA partindo de Palo Alto, CA no AS6461, o AS6461 escolhe o caminho com um único salto entre sistemas autônomos, seguindo o que foi dito anteriormente. Pela outra opção, teríamos dois saltos. Entretanto, a rota por Chicago imprime uma distância total de 3.584 milhas, enquanto que, por Seatle, a distância seria de 703 milhas. Essa diferença de mais de 2.800 milhas gera aumento de latência e perda de desempenho. Medições feitas em estudos anteriores mostram que aproximadamente 75% das rotas sofrem acréscimo de mais de 15 msec, a principal causa é a escolha de rotas baseada no número de saltos (AS hop count).
fig. 1
Algumas
características são esperadas de um protocolo de
roteamento inter-domínios, como:
- Atender às políticas de roteamento vigentes - o "relacionamento" entre os ASes determina vizinhos que caminho é escolhido quando temos múltiplas opções;
- A partir do item anterior, deve ser capaz de escolher a rota que ofereça o melhor desempenho no caso de ainda termos múltiplas opções. A performance pode ser medida dentro do domínio de um ISP ou pelo atraso entre origem e destino. Ambas as medidas são importantes para aprimorarmos o desempenho local e o global.
A idéia de incorporar informações sobre a localização geográfica na estrutura do endereço IP não é nova. Diversas propostas foram feitas e, apesar de todas terem abordagens diferentes, todas têm a noção fundamental de termos o IP exclusivamente baseado em localização geográfica. Isso tem sido motivo de resistência a tais propostas.
Substituir o atual sistema de endereçamento, mesmo que de forma parcial, por um baseado em localização geográfica não se mostra uma abordagem plausível. No entanto, acrescentar tal informação na estrutura pode trazer uma série de novas funcionalidades e políticas de roteamento. Ao invés de utilizarmos a contagem de saltos entre "ASes" antes mencionada, podemos escolher caminhos que tenham uma distância final menor. A figura 2 mostra a relação distância X atraso. Um atraso menor pode ser um benefício para aplicações "real-time", por exemplo. Além disso, distâncias maiores podem oferecer uma maior probabilidade de problemas de tráfego.
Endereçamento no GIRO:
Para incorporar a
informação geográfica na estrutura de
endereçamento, foi definido um novo formato chamado de
endereço GIRO. Ele é composto de duas partes:
externa e interna. A parte externa tem regras de
formação semelhantes ao prefixo
do IP no BGP e é usada para roteamento
inter-domínios. Ela composta por:
- ID da rede sob a forma do número do sistema autônomo (ASN - AS Number);
- Localização Geográfica (geolocation);
- Traffic slice ID - SID
Chamamos essa parte (ASN.geolocation.SID) de prefixo GIRO (G-prefix).
O componente interno é formado pela sub-rede e pela parte do host, de maneira similar ao que ocorre no endereço IP. Ele é usado para o roteamento dentro da rede destino, ou seja, a nível de intra-domínio. Na figura 3, temos a estrutura do endereço GIRO.
O componente interno é formado pela sub-rede e pela parte do host, de maneira similar ao que ocorre no endereço IP. Ele é usado para o roteamento dentro da rede destino, ou seja, a nível de intra-domínio. Na figura 3, temos a estrutura do endereço GIRO.
fig. 3
Um prefixo GIRO
é anunciado na internet pela sua rede de origem
através do BGP. O prefixo GIRO é,
então, agregado à tabela de roteamento. Como foi
mostrado, o primeiro campo é o ASN, isso representa uma das
diferenças em relação às
propostas anteriores. Dessa forma, podemos garantir que os pacotes
sempre chegarão corretamente às suas respectivas
redes-destino, além disso, é possível
basearmos nesse ID as políticas de roteamento que existe
atualmente. Portanto, a informação
geográfica serve como uma dica secundária nas
decisões de roteamento - ao contrário do que fora
proposto em outros trabalhos. No caso de uma rede não possui
um ASN, será usado o do seu provedor. Se essa rede tiver
vários provedores, ela terá diversos prefixos
GIRO.
fig. 4
Agregação de rotas:
Com a estrutura de endereçamento GIRO, é possível encontrarmos diferentes tipos de agregação de rotas: por ASN, por localização geográfica e por SID. Podemos agregar entradas da tabela de roteamento se os seus prefixos são contínuos e se os seus níveis AS forem iguais. Na figura 4, temos B.US.CA.LA e B.US.CA.SF, que são agregados e representados por B.US.CA. Essa agregação é passada de "A" para "E". Outro exemplo de agregação seria se tivéssemos a mesma rota AS (ASPATH) para alcançar os diferentes prefixos. Os diferentes tipos de agregação podem nos levar a um mesmo resultado: redução da tabela global de roteamento.
Adicionando informações geográficas das "bordas":
A informação geográfica é adicionada aos roteadores através do cálculo da distância entre cada sistema autônomo (AS). Na figura 5, vemos que a rota [A B C] passa pelos diferentes sistemas (ASes) através de roteadores de entrada e de saída. Cada um deles, baseado em informação geográfica, calcula a distância ao roteador de entrada/saída anterior e publica a distância nos anúncios BGP. Dessa forma, é possível saber a distância final das diferentes rotas possíveis e, com isso, escolher a que for mais curta.
OBS.: Como falamos, no GIRO, os roteadores das "bordas" dos sistemas autônomos anunciam a distância física até o roteador de borda vizinho. Outra opção seria anunciar a sua posição absoluta em termos de latitude e longitude. Essa abordagem traz vantagens se tivermos problemas permanentes em determinadas regiões, por exemplo.
Escolha das rotas:
fig. 6 - Os itens em negrito (2, 5 e 8) representam as mudanças com o uso do GIRO.
O segundo campo do
prefixo GIRO (localização geográfica)
contém bits que informam a latitude e a longitude.
Dependendo do número de bits usados, temos uma
precisão maior ou menor em relação
à localização. Usaremos País.Estado.Cidade.
O terceiro campo, SID,
é bastante importante quando temos mais de uma maneira de
chegar ao destino. Na figura 4 abaixo, temos esse exemplo. Observe a
tabela de "A" que é propagada para "E". Temos duas maneiras
de chegarmos ao roteador de nova york que se encontra no AS C. Para uma
delas, temos SID igual a 0, para a outra, igual a 1.
fig. 4
Obs.: GIRO não dá suporte a "anycast" da maneira
que vemos no atual sistema de roteamento.
Agregação de rotas:
Com a estrutura de endereçamento GIRO, é possível encontrarmos diferentes tipos de agregação de rotas: por ASN, por localização geográfica e por SID. Podemos agregar entradas da tabela de roteamento se os seus prefixos são contínuos e se os seus níveis AS forem iguais. Na figura 4, temos B.US.CA.LA e B.US.CA.SF, que são agregados e representados por B.US.CA. Essa agregação é passada de "A" para "E". Outro exemplo de agregação seria se tivéssemos a mesma rota AS (ASPATH) para alcançar os diferentes prefixos. Os diferentes tipos de agregação podem nos levar a um mesmo resultado: redução da tabela global de roteamento.
Adicionando informações geográficas das "bordas":
A informação geográfica é adicionada aos roteadores através do cálculo da distância entre cada sistema autônomo (AS). Na figura 5, vemos que a rota [A B C] passa pelos diferentes sistemas (ASes) através de roteadores de entrada e de saída. Cada um deles, baseado em informação geográfica, calcula a distância ao roteador de entrada/saída anterior e publica a distância nos anúncios BGP. Dessa forma, é possível saber a distância final das diferentes rotas possíveis e, com isso, escolher a que for mais curta.
fig. 5
OBS.: Como falamos, no GIRO, os roteadores das "bordas" dos sistemas autônomos anunciam a distância física até o roteador de borda vizinho. Outra opção seria anunciar a sua posição absoluta em termos de latitude e longitude. Essa abordagem traz vantagens se tivermos problemas permanentes em determinadas regiões, por exemplo.
Escolha das rotas:
Agora vamos ver como
fica a nova seqüência de passos para a escolha de
uma determinada rota. Na figura 6, temos uma tabela que mostra tal
seqüência. Como podemos ver, a antiga contagem de
saltos (AS hop count) foi substituída pela
distância física entre os pontos origem/destino.
Observe a tabela:
fig. 6 - Os itens em negrito (2, 5 e 8) representam as mudanças com o uso do GIRO.
Devemos levar em
consideração que, para pequenas
distâncias, podemos não ter uma
aplicação tão eficiente da
política da menor distância, já que ela
é medida em milhas. Por isso, no item 2, temos o
parâmetro δ, que serve para ajustarmos a
dimensão da distância que estamos tratando, ou
seja, se queremos uma análise local ou global. Mesmo assim,
ainda podemos ter diversas opções após
o passo 2, então, vamos ao passo da contagem de saltos.
Escolha do ponto de
saída:
No BGP, quando temos uma preferência igual e a mesma contagem de salto para duas diferentes rotas, o próximo passo é comparar os pontos de saída. Isso significa que será escolhida a rota que contém o ponto de saída mais próximo (early-exit). No entanto, essa abordagem não representa, de fato, a escolha do melhor caminho. Foi apresentada, então, uma nova opção: o ponto de entrada/saída que está na rota origem/destino mais curta (shortest-path). Porém, apesar de essa nova abordagem trazer bons resultados a nível global, ainda é preciso compará-la com a anterior (early-exit) a nível local. Isso porque é preciso avaliar as conseqüências de escolher um roteador que proporciona uma maior distância percorrida localmente (dentro de um certo sistema autônomo).
No BGP, quando temos uma preferência igual e a mesma contagem de salto para duas diferentes rotas, o próximo passo é comparar os pontos de saída. Isso significa que será escolhida a rota que contém o ponto de saída mais próximo (early-exit). No entanto, essa abordagem não representa, de fato, a escolha do melhor caminho. Foi apresentada, então, uma nova opção: o ponto de entrada/saída que está na rota origem/destino mais curta (shortest-path). Porém, apesar de essa nova abordagem trazer bons resultados a nível global, ainda é preciso compará-la com a anterior (early-exit) a nível local. Isso porque é preciso avaliar as conseqüências de escolher um roteador que proporciona uma maior distância percorrida localmente (dentro de um certo sistema autônomo).
Na figura 7, podemos ver um
exemplo de dois domínios vizinhos que se conectam por
três diferentes pontos. As ligações
são exibidas como g|w
(g
representa a distância geográfica e w o peso IGP). As
ligações inter-domínios possuem o
valor da distância física (R1-R4, R2-R5 e R3-R6).
Vamos imaginar que R0 quer encontrar o caminho com o menor custo para
chegar a R7. Nesse caso, ele precisa combinar os pesos (custos) dos
dois domínios (A e B). No entanto, isso é uma
tarefa complicada, pois as unidades de medida dos sistemas
autônomos podem ser diferentes. Além disso, os
pesos das ligações inter-domínios
não são conhecidos, sabemos apenas a
distância física - que é adquirida
através dos anúncios de rotas do BGP, conforme
foi explicado. No entanto, ao invés de usarmos os pesos,
pode-se usar a distância geográfica para encontrar
o caminho mínimo de R0 a R7.
fig. 7
fig. 7
Temos três
maneiras de escolher o ponto de saída:
- "Early-exit": É escolhido o ponto que minimiza o custo (não a distância) no domínio local. Na fig.7, o R1.
- "Late-exit": É escolhido o ponto que minimiza o custo que teremos no domínio vizinho. Na fig.7, o R3.
- "Shortest-path": É escolhido o ponto que minimiza a distância física, não o custo, entre origem (R0) e destino (R7). Com essa estratégia, é possível atingir uma situação ideal em que também temos o custo minimizado, foi o que aconteceu neste exemplo. Na rota do meio, temos o menor custo total (custo dos domínios A e B) e, ainda, a menor distância física.
Seleção
de rotas entre domínios:
Usando-se os passos da figura 6 para comprar o desempenho GIRO X BGP, foi confirmado o melhor desempenho do GIRO. Para aproximadamente 20% das rotas houve uma redução de até 40% do custo em relação ao BGP. O caso que tivemos na figura 1 foi identificado na simulação.
Escolha do ponto de
saída:
Foram aplicadas as técnicas "Early-exit", "Late-exit" e "Shortest-path" (apresentadas na seção "Arquitetura"). Os gráficos abaixo mostram a comparação do desempenho das duas últimas comparadas com a primeira ("Early-exit"), que é a utilizada atualmente pelo BGP.
fig.8
fig.9
Na fig.8, podemos ver que o
desempenho do uso de "Late-exit" difere em 20% do uso de "Early-exit".
Em alguns casos houve ganho, em outros perda de performance.
Já no caso do uso de "Shortest-path", não houve
perda e, ainda, houve ganho em 30% dos casos. Repare que a figura 8
trata de uma análise global.
Na fig.9, temos uma análise local que confirma o que foi dito anteriormente foi dito: para pequenas distâncias, o uso de "Shortest-path" não parece ser uma opção tão eficiente. Para ambas as técnicas que estão no gráfico, vemos que menos de 18% dos casos apresentaram perda de desempenho em relação ao "Early-exit" e, em aproximadamente 12% dos casos, houve ganho.
O uso da política "Shortest-path" para trazer ganhos conideráveis num âmbito geral, pois é consideravelmente superior às outras a nível global.
fig.10
Na fig.9, temos uma análise local que confirma o que foi dito anteriormente foi dito: para pequenas distâncias, o uso de "Shortest-path" não parece ser uma opção tão eficiente. Para ambas as técnicas que estão no gráfico, vemos que menos de 18% dos casos apresentaram perda de desempenho em relação ao "Early-exit" e, em aproximadamente 12% dos casos, houve ganho.
O uso da política "Shortest-path" para trazer ganhos conideráveis num âmbito geral, pois é consideravelmente superior às outras a nível global.
Agregações:
Neste ponto, temos a análise das tabelas de roteamento. Foi feito um mapeamento geográfico do BGP através do "GeoLite city". Em seguida, como as tabelas GIRO dependem da posição geográfica do roteador, foram feitos testes em quatro roteadores em pontos geográficos distintos: Estados Unidos, Rússia, Japão e Reino Unido.
Na fig.10, temos a comparação do tamanho das tabelas: BGP com prefixos que não puderam ser mapeados geograficamente, BGP com prefixos mapeados e GIRO.
Neste ponto, temos a análise das tabelas de roteamento. Foi feito um mapeamento geográfico do BGP através do "GeoLite city". Em seguida, como as tabelas GIRO dependem da posição geográfica do roteador, foram feitos testes em quatro roteadores em pontos geográficos distintos: Estados Unidos, Rússia, Japão e Reino Unido.
Na fig.10, temos a comparação do tamanho das tabelas: BGP com prefixos que não puderam ser mapeados geograficamente, BGP com prefixos mapeados e GIRO.
fig.10
Na fig.11, temos a
porcentagem de cada tipo de agregação de prefixos
GIRO dos roteadores de cada região, dessa forma,
é possível o impacto das diferentes
agregações no tamanho da tabela. Repare que
apenas o prefixo simples ASN não traz
informações geográficas e representa
aproximadamente 40% dos casos. Assim, aproximadamente 60% dos prefixos
GIRO vieram de agregações geográficas
e proporcionaram o resultado visto na fig.10.
fig.11
topo
Pode-se concluir que o uso prático dessa proposta de roteamento e endereçamento em escala mundial pode trazer um ganho de desempenho considerável. Além disso, diminuir de forma expressiva o tamanho das tabelas de roteamento. Por fim, novas políticas de roteamento podem ser criadas a partir da informação geográfica que agora teremos em mãos. Tudo isso pode ser feito sem que as atuais políticas de roteamento sejam prejudicadas, o que torna essa proposta viável.
- "GIRO" - Geographically Informed Inter-Domain Routing (2007 - Ricardo Oliveira, Mohit Lad, Beichuan Zhang, Lixia Zhang)
- A Survey on Position-Based Routing in Mobile Ad-Hoc Networks (2001 - Martin Mauve, Jörg Widmer, Hannes Hartenstein)
