A Internet, onforme expli amos naseção 2.1 , pode ser vista omoum onjunto desistemas
aut nomos inter one tados. Uma tabela BGP ontém diversos aminhos dados em termos
de identi adores de sistemas aut nomos. Assim, apartir de tal tabela, é possível onstruir
um grafono qual osvérti es orrespondem a sistemas aut nomose as arestas orrespondem
a links entre roteadores de borda de sistemas aut nomos adja entes. Chamamos esse grafo
de mapa topológi o daInternet ao nível de sistemas aut nomos.
Quando se fala em roteamento, pode-se dizer que a internet de ada sistema aut nomo
é essen ialmente omposta de roteadores que inter one tam as diversas redes físi as desse
sistemaaut nomoe/ou one tamredesdessessistemasaredesdesistemasvizinhos. Portanto,
outraformadeenxergaraInterneté omoumgrafoemquevérti es orrespondemaroteadores
e arestas orrespondem a links entre esses roteadores. Esse grafoé bem maisdetalhado que
o mapa ao nível de sistemas aut nomos, uma vez que ada sistema aut nomo possui, em
geral,diversosroteadores. Chamamos essegrafodemapatopológi odaInternetao nível de
roteadores.
Ao ontráriodoqueo orre omo asodomapatopológi oaoníveldesistemasaut nomos,
não existe uma tabela de roteamento que liste as onexões entre todos os roteadores da
Internet. Assim, mapear a Internet ao nível de roteadores envolve outras té ni as, sendo a
prin ipal delas ouso detra eroute.
O tra eroute é um programa que tenta obter os endereços IP de todos os roteadores
existentes no aminho entredois nósda Internet. Ele fun iona ombinandodois artifí ios: o
ampotime-to-live (TTL) dospa otes IPe aexistên ia deumproto olonoti açãode erros
denominadoInternetControlMessagesProto ol (ICMP).Esseproto oloéimplementadopela
grande maioria dos roteadores da Internet. O ampo TTL é um ampo no pa ote IP que é
indi andoqueopa oteper orreuum aminhomuitolongoenão onseguiu hegaraodestino
(isso pode o orrer em asos de falhas ou mudanças no roteamento). Assim, se o programa
tra eroute sendo exe utado em uma máquina A quer des obrir os endereços IP de todos os
roteadoresexistentes entreAeB, eleini ialmente enviaumpa ote omdestinoaBmas om
TTL iguala 1. Oprimeiro roteador
R
1
no aminho de rementará o ampo TTL e noti aráA, om um pa ote ICMP, que o pa ote não onseguiu hegar até o destino B. Esse pa ote
ICMP onterá, noseu ampo origem, oendereço 2
IP doroteador
R
1
. Em seguida A enviaráumpa ote omdestino aB e om TTL igual a2. Osegundo roteador
R
2
no aminho entreA e B responderá om um pa ote ICMP. Daí poderemos on luir que existe um link entre
R
1
eR
2
,se assumirmos que o segundo pa ote tomou o mesmo aminho que o primeiro 3. O
programarodando emAsegue enviando pa otes omTTL in rementais parades obrirtodos
osroteadoresno aminho entreA eB.
A seção 3.4.2 detalha omo os dados de tra eroute podem ser usados para riar mapas
topológi osao nível deroteadores.
2.3.1 Topologias usadas neste trabalho
Diversos trabalhos que estudam proto olos de rede realizam simulações em grafos orres-
pondentes a topologias reais da Internet. Parte deles utiliza topologias ao nível de sistemas
aut nomos, que podem ser obtidas, por exemplo, através de tabelas BGP [37℄ extraídas de
roteadoresdeborda. Outrapartedessestrabalhosutilizatopologiasmaisdetalhadas,aonível
deroteadores,isto é,ao nívelde one tividadeIP.Tais topologias podemserobtidas através
demedidasativasentrediversospontosespalhadospelaInternet. Otipodemedidaativamais
omum é a gerada pelo omando tra eroute. Em asos em que sepro ura analisar a banda
média de rede gasta por determinado proto olo de distribuição de dados, ou mais pre isa-
mente,oganhopoten ialmáximo quesepodeobter omtalproto olo, emgeralpre isa-sede
umgraumaiordepre isãonatopologia eassimpreferem-setopologiasnonívelderoteadores.
Issoporqueem topologiasao nívelde sistemas aut nomosnão é possíveldeterminar ogasto
ombanda deredenointeriordossistemasaut nomos,umavezquenãosesabeporquantos
links se passa ao atravessar um sistema aut nomo e essa quantidade de links atravessados
podevariar bastante de umsistemaaut nomo para outro.
Considere por exemplo a gura 2.1 , que mostra em nível de sistemas aut nomos e em
nível de roteadores a topologia existente entre um servidorS e dois sites lientes A e B. Os
quatro sistemas aut nomos estãodelimitados por elipses rotuladas
A
i
. Vimos, na seção 1.2 ,queépossível riarumaárvorealternativaàdos aminhosmais urtosnessatopologiaeobter
umae onomiaemtermosdebandade rede onsumida. Se,noentanto,analisarmosa mesma
2
Maispre isamente,umdosendereçosIPdoroteador.
3
Infelizmentenãoétãoin omumquearotamude. Issoreduza on abilidadedousodetra eroutes para
inferir atopologia aonívelderoteadores, por isso é ne essárioque seexe uteo omandováriasvezes para
Figura2.1: Uma topologia simplesaosníveisde sistemas aut nomose deroteadores.
topologia ao nível de sistemas aut nomos, vemos que existe apenas uma árvore possível: o
site A estarialigado ao servidorSatravésdo aminho
SA
2
A
eo site Bpelo aminhoSA
2
B
.Assim,omenordetalhamentodatopologia aoníveldesistemasaut nomospodees onder
ganhospoten iaisobteníveis omousode orestasdedistribuiçãoalternativasàdos aminhos
mais urtos. Por esse motivo, neste trabalho fo amos em topologias ao nível de roteadores.
O apítulo 4mostra omoessastopologias foramobtidas.
2.3.2 Topologias sintéti as
A obtenção de topologias reais, em nível de roteadores, para a análise dos proto olos de
riação de orestas de distribuição não é uma tarefa fá il. Por esse motivo, este trabalho
utiliza-se também de topologias sintéti as ao nível de roteadores. O GT-ITM [12℄ é um
programa apazdesintetizartopologiasaonívelderoteadores. Tentando tornarastopologias
mais realistas, o GT-ITM ini ialmente ria uma topologia em nível de sistemas aut nomos,
de a ordo om parâmetros que ontrolam o número de nós e a sua one tividade. Esses
sistemas aut nomos são lassi ados em de trânsito e stubs. Os sistemas aut nomos de
trânsito orrespondem, na Internet real, a sistemas aut nomos de provedores de tráfego,
que formam o ba kbone da Internet. Sistemas aut nomos stub sãoaqueles que não provêem
tráfego para outros sistemas aut nomos, mas sim apenas a eitam tráfego destinado a eles
mesmos e enviamtráfego originado neles mesmos. OGT-ITM pro ura riar topologias mais
realistas ao re etir a estrutura hierárqui a existente entre provedores de tráfego e sistemas
stub.
orrespondente a um sistema aut nomo em um outro grafo, este orrespondente à internet
(istoé,arede aonívelde roteadores) desse sistemaaut nomo.
Neste trabalho utilizamos, além de topologias reais, topologias ao nível de roteadores
geradaspeloGT-ITM paraanalisar proto olos para riação de árvores dedistribuição, omo
veremosno apítulo6.