cap4b-2011

4: Camada de Rede4b-*Captulo 4: Camada de Rede4.5 Algoritmos de roteamentoEstado de enlaceVetor de distnciasRoteamento hierrquico4.6 Roteamento na InternetRIPOSPFBGP4.7 Roteamento broadcast e multicast4. 1 Introduo4.2 Redes de circuitos virtuais e de datagramas4.3 O que h dentro de um roteador4.4 O protocolo da Internet (IP)Formato do datagramaEndereamento IPv4ICMPIPv6IPSec

4: Camada de Rede

4: Camada de Rede4b-*1230111valor no cabealhodo pacote que estchegandoAlgoritmo de roteamentotabela de repasse localvalor cabealholink sada01000101011110013221Relacionamento entre roteamento e repasse

4: Camada de Rede

4: Camada de Rede4b-*Grafo: G = (N,E)

N = conj. de roteadores = { u, v, w, x, y, z }

E = conj. de enlaces ={ (u,v), (u,x), (u,w), (v,x), (v,w), (x,w), (x,y), (w,y), (w,z), (y,z) }Abstrao com grafosComentrio: a abstrao com grafos til em outros contextos da rede

Exemplo: P2P, onde N o conj. dos pares e E o conj. das conexes TCP

4: Camada de Rede

4: Camada de Rede4b-*Abstrao com grafos: custos c(x,x) = custo do enlace (x,x)

- p.e., c(w,z) = 5

custo poderia tambm ser 1, ou inversamente relacionado banda,ou inversamente relacionado ao congestionamentoCusto do caminho (x1, x2, x3,, xp) = c(x1,x2) + c(x2,x3) + + c(xp-1,xp) P: Qual o caminho de menor custo entre u e z?Algoritmo de roteamento: algoritmo que encontra o caminho de menor custo

4: Camada de Rede

4: Camada de Rede4b-*Classificao de Algoritmos de RoteamentoInformao global ou descentralizada/local?Global:todos roteadores tm conhecimento completo da topologia e custos dos enlacesalgoritmos de estado de enlaceDescentralizada/local: roteador conhece vizinhos diretos e custos at elesprocesso iterativo de clculo, troca de infos com vizinhosAlgoritmo de vetor de distnciasEstticos ou dinmicos?Estticos: rotas mudam lentamente com o tempoDinmicos: rotas mudam mais rapidamenteatualizao peridicaem resposta a mudanas nos custos dos enlaces

4: Camada de Rede


4: Camada de Rede

4: Camada de Rede4b-*O algoritmo de roteamento de estado de enlace (LS Link State)Algoritmo de Dijkstratopologia da rede, custos dos enlaces conhecidos por todos os nsrealizado atravs de difuso do estado dos enlaces todos os ns tm mesma info.calcula caminhos de menor custo de um n (origem) para todos os demaisgera tabela de rotas para aquele niterativo: depois de k iteraes, sabemos menor custo p/ k destinosNotao:c(x,y): custo do enlace do n x ao n y. custo infinito se no forem vizinhos diretosD(v): valor corrente do custo do caminho da origem ao destino vp(v): n antecessor no caminho da origem ao n v, imediatamente antes de vN: conjunto de ns cujo caminho de menor custo j foi determinado

4: Camada de Rede

4: Camada de Rede4b-*O algoritmo de Dijkstra1 Inicializao: 2 N = {u} 3 para todos os ns v 4 se v for um vizinho do n u 5 ento D(v) = c(u,v) 6 seno D(v) = 7 8 Loop9 encontre w no contido em N tal que D(w) um mnimo 10 adicione w ao conjunto N 11 atualize D(v) para cada vizinho v de w e ainda no em N: 12 D(v) = min( D(v), D(w) + c(w,v) ) 13 /* o novo custo ao n v o custo velho a v ou o custo do 14 menor caminho conhecido para w, mais o custo de w a v */ 15 at que todos os ns estejam em N

4: Camada de Rede

4: Camada de Rede4b-*Algoritmo de Dijkstra: exemploEtapa012345N'uuxuxyuxyvuxyvwuxyvwzD(v),p(v)2,u2,u2,uD(w),p(w)5,u4,x3,y3,yD(x),p(x)1,uD(y),p(y)2,xD(z),p(z) 4,y4,y4,y

4: Camada de Rede

4: Camada de Rede4b-*Algoritmo de Dijkstra: exemplo rvore de caminhos mnimos resultante originada em u:Tabela de repasse resultante em u:

4: Camada de Rede

4: Camada de Rede4b-*Algoritmo de Dijkstra, discussoComplexidade algoritmica: n nsa cada iterao: precisa checar todos ns, w, no em Nn*(n+1)/2 comparaes => O(n2)implementaes mais eficientes possveis: O(nlogn)Oscilaes possveis:p.ex., custo do enlace = carga do trfego carregado11+ee0e110002+e1+e100inicialmente recalcularotas recalcula recalcula

4: Camada de Rede


4: Camada de Rede

4: Camada de Rede4b-*O algoritmo de Vetor de Distncias (DV)Equao de Bellman-Ford (programao dinmica)Definedx(y) := custo do caminho de menor custo entre x e y

Ento

dx(y) = min {c(x,v) + dv(y) }

onde min tomado entre todos os vizinhos v de xv

4: Camada de Rede

4: Camada de Rede4b-*Exemplo com Bellman-FordClaramente, dv(z) = 5, dx(z) = 3, dw(z) = 3du(z) = min { c(u,v) + dv(z), c(u,x) + dx(z), c(u,w) + dw(z) } = min {2 + 5, 1 + 3, 5 + 3} = 4O n que leva ao custo mnimo o prximo passoao longo do caminho mais curto tabela de repasseA equao B-F diz:

4: Camada de Rede

4: Camada de Rede4b-*Algoritmo de Vetor de DistnciasDx(y) = estimativa do menor custo entre x e yN x sabe o custo para cada vizinho v: c(x,v)N x mantm o vetor de distncias Dx = [Dx(y): y N ]N x mantm ainda os vetores de distncias dos seus vizinhosPara cada vizinho v, x mantm Dv = [Dv(y): y N ]

4: Camada de Rede

4: Camada de Rede4b-*Algoritmo de Vetor de DistnciasIdia bsica: Cada n envia periodicamente o seu prprio vetor de distncias estimadas para os vizinhosQuando um n x recebe um novo DV com as estimativas de um vizinho, ele atualiza o seu DV usando a equao B-F:Dx(y) minv{c(x,v) + Dv(y)} p/ cada n y NSob condies mnimas, naturais, a estimativa Dx(y) converge para o menor custo real dx(y)

4: Camada de Rede

4: Camada de Rede4b-*Algoritmo de Vetor de DistnciasIterativo, assncrono: cada iterao local causada por: mudana do custo do enlace localmensagem do vizinho: mudana de caminho de menor custo para algum destinoDistribudo:cada n avisa a seus vizinhos apenas quando muda seu caminho de menor custo para qualquer destinoos vizinhos ento avisam a seus vizinhos, se for necessrioCada n:

4: Camada de Rede

Network Layer4-*origemorigemx y zxyz0origemcusto parax y zxyzcusto parax y zxyz710custo para2 0 1 2 0 17 1 0tempoTabela n xTabela n yTabela n zDx(y) = min{c(x,y) + Dy(y), c(x,z) + Dz(y)} = min{2+0 , 7+1} = 2Dx(z) = min{c(x,y) + Dy(z), c(x,z) + Dz(z)} = min{2+1 , 7+0} = 332

Network Layer

Network Layer4-*origemorigemx y zxyz0 2 3origemcusto parax y zxyz0 2 3origemcusto parax y zxyzcusto parax y zxyz0 2 7origemcusto parax y zxyz0 2 3origemcusto parax y zxyz0 2 3origemcusto parax y zxyz0 2 7origemcusto parax y zxyz710custo para2 0 1 2 0 17 1 02 0 17 1 02 0 13 1 02 0 13 1 02 0 13 1 02 0 13 1 0tempoTabela n xTabela n yTabela n zDx(y) = min{c(x,y) + Dy(y), c(x,z) + Dz(y)} = min{2+0 , 7+1} = 2Dx(z) = min{c(x,y) + Dy(z), c(x,z) + Dz(z)} = min{2+1 , 7+0} = 3

Network Layer

4: Camada de Rede4b-*Vetor de Distncias: mudanas no custo dos enlacesMudanas no custo dos enlaces:n detecta mudana no custo do enlace localatualiza tabela de distnciasse mudou o VD, avisa aos vizinhosboasnotciaschegamlogoNo tempo t0, y detecta a mudana no custo do enlace, atualiza oseu VD e informa os vizinhos.

No tempo t1, z recebe a atualizao de y e atualiza a sua tabela. Computa o novo menor custo p/ x e envia o seu VD p/ os vizinhos.

No tempo t2, y recebe a atualizao de z e atualiza a sua tabela. Os custos mnimos de y no mudam e portanto y no envia nenhuma mensagem para z.

4: Camada de Rede

4: Camada de Rede4b-*Vetor de Distncias: mudana no custo dos enlacesMudana no custo dos enlaces:boas notcias chegam logo ms notcias demoram para chegar - problema da contagem at o infinito! 44 iteraes antes do algoritmo estabilizar: veja textoReverso envenenada: Se z roteia via y p/ chegar a x:z informa p/ y que sua distncia p/ x infinita (p/ que y no roteie p/ x via z)ser que isto resolve completamente o problema da contagem at o infinito?

4: Camada de Rede

4: Camada de Rede4b-*Comparao dos algoritmos LS e DVComplexidade das mensagensLS: com n ns, E enlaces, O(nE) mensagens enviadasDV: trocar mensagens apenas entre vizinhosvaria o tempo de convergnciaVelocidade de ConvergnciaLS: algoritmo O(n2) requer O(nE) mensagenspodem ocorrer oscilaesDV: varia tempo para convergirpodem ocorrer rotas cclicasproblema de contagem ao infinitoRobustez: o que acontece se houver falha do roteador?LS: n pode anunciar valores incorretos de custo de enlacecada n calcula sua prpria tabelaDV:um n VD pode anunciar um custo de caminho incorretoa tabela de cada n usada pelos outros nsum erro propaga pela rede

4: Camada de Rede


4: Camada de Rede

4: Camada de Rede4b-*Roteamento Hierrquicoescala: com 200 milhes de destinos:impossvel guardar todos destinos na tabela de rotas!troca de tabelas de rotas afogaria os enlaces!

autonomia administrativainternet = rede de redescada admin de rede pode querer controlar roteamento em sua prpria redeNeste estudo de roteamento fizemos uma idealizao:todos os roteadores idnticosrede no hierarquizada (flat) no verdade, na prtica

4: Camada de Rede

4: Camada de Rede4b-*Roteamento Hierrquicoagregar roteadores em regies, sistemas autnomos (ASs)roteadores no mesmo AS usam o mesmo protocolo de roteamentoprotocolo de roteamento intra-ASroteadores em ASs diferentes podem usar diferentes protocolos de roteamento intra-ASRoteadores de bordaEnlace direto para roteador em outro AS

4: Camada de Rede

4: Camada de Rede4b-*ASs interconectadosTab. de encaminhamento configurada pelos algoritmos intra-AS e inter-ASIntra-AS define entradas p/ dest. internosInter-AS e Intra-AS definem entradas p/ dest. externos

4: Camada de Rede

4: Camada de Rede4b-*Tarefas do roteamento inter-ASSuponha que um roteador no AS1 recebe um datagrama cujo destino est fora do AS1Roteador deveria repassar o pacote p/ um dos roteadores de borda, mas qual?AS1 precisa:aprender quais destinos so alcanveis via o AS2 e quais so alcanveis via o AS3propagar estas info. de alcanabilidade para todos os roteadores no AS1Tarefas do rot. inter-AS!

4: Camada de Rede

4: Camada de Rede4b-*Exemplo: definindo a tabela de repasse no roteador 1dSuponha que o AS1 aprende (atravs do protocolo inter-AS) que a sub-rede x alcanvel via o AS3 (rot. de borda 1c) mas no via o AS2.Protocolo Inter-AS propaga info. de alcanabilidade para todos os roteadores internos.Roteador 1d determina atravs de info. de roteamento intra-AS que sua interface I est no caminho mnimo para 1c.Coloca par (x,I) na tab. de repasse.

4: Camada de Rede

4: Camada de Rede4b-*Exemplo: Escolhendo entre mltiplos ASesSuponha que o AS1 aprenda atravs do protocolo inter-AS que a subrede x seja alcanvel de AS3 e de AS2.Para configurar a tabela de repasse, o roteador 1d deve determinar para qual gateway ele deve encaminhar pacotes para o destino x. Isto tambm uma tarefa do protocolo de roteamento inter-AS!

x

4: Camada de Rede

4: Camada de Rede4b-*Exemplo: escolhendo entre mltiplos ASsSuponha agora que o AS1 aprende atravs do protocolo inter-AS que a sub-rede x alcanvel via AS3 e via AS2.Para configurar a tabela de encaminhamento, o roteador 1d deve determinar para qual roteador de borda ele deve enviar pacotes com destino x .Isto tambm tarefa do protocolo de roteamento inter-AS!Roteamento da batata quente (hot potato): envia pacote para o roteador de borda mais prximo.

4: Camada de Rede


4: Camada de Rede

4: Camada de Rede4b-*Roteamento Intra-ASTambm conhecidos como protocolos de roteadores internos (IGP - Interior Gateway Protocols )Os protocolos de roteamento Intra-SA mais comuns so:

RIP: Routing Information Protocol

OSPF: Open Shortest Path First

IGRP: Interior Gateway Routing Protocol (proprietrio da Cisco)

4: Camada de Rede


4: Camada de Rede

4: Camada de Rede4b-*RIP (Routing Information Protocol)Algoritmo vetor de distnciasIncludo na distribuio do BSD-UNIX em 1982Mtrica de distncia: n de saltos (enlaces) (mx = 15 enlaces)Do roteador A p/ sub-redes:

4: Camada de Rede

4: Camada de Rede4b-*Anncios RIPVetores de distncias: trocados a cada 30 seg via Mensagem de Resposta (tambm chamada de anncio)Cada anncio: rotas para at 25 redes destino dentro do AS

4: Camada de Rede

4: Camada de Rede4b-*Exemplo RIPSub-Rede Prximo Roteador No. de saltos at o destino destino wA2yB2 zB7x--1......wxyzACDBTabela de rotas/repasse em D...

4: Camada de Rede

4: Camada de Rede4b-*Exemplo RIPSub-Rede destino Prximo Roteador No. de saltos wA2yB2 zB A7 5x--1......wxyzACDBTabela de rotas/repasse em D... Dest Prox Saltos w - 1 x - 1 z C 4 . ...Anncios deA para D

4: Camada de Rede

4: Camada de Rede4b-*RIP: Falha e Recuperao de Enlaces Se no for recebido anncio novo durante 180 seg --> vizinho/enlace declarados mortosrotas via vizinho invalidadasnovos anncios enviados aos vizinhosna sua vez, os vizinhos publicam novos anncios (se foram alteradas as suas tabelas)informao sobre falha do enlace rapidamente propaga para a rede inteirareverso envenenada usada para impedir rotas cclicas (ping-pong) (distncia infinita = 16 enlaces)

4: Camada de Rede

4: Camada de Rede4b-*RIP: Processamento de tabelasTabelas de repasse RIP gerenciadas por processo de nvel de aplicao chamado route-d (routing daemon)anncios enviados periodicamente em pacotes UDP

4: Camada de Rede


4: Camada de Rede

4: Camada de Rede4b-*OSPF (Open Shortest Path First)open (aberto): publicamente disponvelUsa algoritmo do Estado de Enlaces (LS)disseminao de pacotes LSmapa da topologia em cada nclculo de rotas usando o algoritmo de DijkstraAnncio de OSPF inclui uma entrada por roteador vizinhoAnncios disseminados para AS inteiro (via inundao)Carregados em mensagens OSPF diretamente sobre IP (ao invs de TCP ou UDP)

4: Camada de Rede

4: Camada de Rede4b-*OSPF: caractersticas avanadas (no existentes no RIP)Segurana: todas mensagens OSPF autenticadas (para impedir intruso maliciosa)Caminhos mltiplos de igual custo (o RIP permite e usa apenas uma rota)Suporte integrado para roteamento unicast e multicast: OSPF multicast (MOSPF) usa mesma base de dados de topologia usado pelo OSPFOSPF hierrquico em domnios grandes.

4: Camada de Rede

4: Camada de Rede4b-*OSPF Hierrquico

4: Camada de Rede

4: Camada de Rede4b-*OSPF HierrquicoHierarquia de dois nveis: rea local, backbone.Anncios de LS disseminados apenas na mesma rea cada n possui topologia detalhada da rea; apenas sabe a direo (caminho mais curto) para redes em outras reas.Roteador de borda de rea: sumariza distncias s redes na sua prpria rea, anuncia a outros roteadores de fronteira de rea.Roteadores de backbone: realizam roteamento OSPF limitado ao backbone.Roteadores de borda: ligam a outros ASs.

4: Camada de Rede


4: Camada de Rede

4: Camada de Rede4b-*Roteamento externo a sistemas autnomos: BGPBGP (Border Gateway Protocol): o padro de fatoBGP prov para cada AS meios de:Obter informao de alcanabilidade (atingibilidade!!!) de sub-redes a partir de ASs vizinhos.Propagar informao de alcanabilidade para todos os roteadores internos ao AS.Determinar boas rotas para sub-redes a partir de informao de alcanabilidade e polticas.Permite que uma sub-rede anuncie a sua existncia para o resto da Internet: Eu existo e estou aqui!

4: Camada de Rede

4: Camada de Rede4b-*O bsico do BGPPar de roteadores (pares BGP) trocam infos de roteamento atravs de conexes TCP semipermanentes TCP: sesses BGPNote que sesses BGP no correspondem a enlaces fsicos.Quando o AS2 anuncia um prefixo para o AS1, ele est prometendo que vai enviar quele prefixo quaisquer datagramas destinados ao mesmo.AS2 pode agregar prefixos nos seus anncios

4: Camada de Rede

4b-*Distribuindo informao de alcanabilidadeCom a sesso eBGP 3a-para-1c, AS3 envia informao de alcanabilidade de prefixos para AS1.1c pode usar iBGP para distribuir esta nova informao de alcance de prefixo para todos os roteadores em AS1.1b pode ento re-anunciar a nova informao de alcance para AS2 atravs da sesso eBGP 1b-para-2a.Quando um roteador aprende sobre um novo prefixo, ele cria uma entrada para o prefixo na sua tabela de repasse.

4: Camada de Rede4b-*Atributos de caminho e rotas BGPQuando um prefixo anunciado, o anncio inclui atributos BGP. prefixo + atributos = rotaDois atributos importantes:AS-PATH: contm os ASs pelos quais o anncio para o prefixo passou: AS 67 AS 17 NEXT-HOP: indica o roteador especfico, interno ao AS, que leva ao AS do prximo salto. (Podem haver mltiplos enlaces do AS atual para o AS do prximo salto)Quando um roteador de borda recebe um anncio de rota, usa a poltica de importao para aceitar/declinar.

4: Camada de Rede

4: Camada de Rede4b-*Seleo de rota do BGPRoteador pode aprender sobre mais de uma rota para algum prefixo. Ele deve selecionar a rota.Regras de eliminao:Valor do atributo preferncia local associado rota: deciso polticaMenor AS-PATH Roteador NEXT-HOP mais prximo: roteamento batata quenteCritrios adicionais

4: Camada de Rede

4: Camada de Rede4b-*Mensagens BGPMensagens BGP trocadas usando TCP.Mensagens BGP:OPEN: abre conexo TCP ao roteador par e autentica remetenteUPDATE: anuncia caminho novo (ou retira velho)KEEPALIVE mantm conexo viva na ausncia de UPDATES; tambm reconhece pedido OPENNOTIFICATION: reporta erros na mensagem anterior; tambm usada para fechar conexo

4: Camada de Rede

4: Camada de Rede4b-*Polticas de roteamento BGPA,B,C so redes de provedoresX,W,Y so clientes (das redes de provedores)X com duas interfaces: conectadas a duas redesX no quer rotear de B para C.. ento X no vai anunciar para B a rota para C

4: Camada de Rede

4: Camada de Rede4b-*Polticas de roteamento BGP (2)A anuncia para B o caminho AW B anuncia para X o caminho BAW Deveria B anunciar para C o caminho BAW?Nem pensar! B no obtm rendimento pelo roteamento CBAW, j que nem W ou C so clientes de BB quer forar C a rotear para W via AB quer rotear apenas para/dos seus clientes!

4: Camada de Rede

4: Camada de Rede4b-*Por que h diferenas entre roteamento Intra-AS e Inter-AS? Polticas: Inter-AS: administrao quer controle sobre como o trfego roteado, quem transita atravs da sua rede. Intra-AS: administrao nica, logo so desnecessrias decises polticasEscalabilidade:roteamento hierrquico economiza tamanho de tabela de rotas, reduz trfego de atualizaoDesempenho: Intra-AS: pode focar em desempenhoInter-AS: polticas podem ser mais importantes do que desempenho

4: Camada de Rede


4: Camada de Rede

4: Camada de Rede4b-*duplicao na fonteduplicaodentro da redecriao/transmisso duplicadaduplicaoRoteamento BroadcastEnvia pacotes de um n para todos os outros nsDuplicao na fonte ineficiente:Duplicao na fonte: como a fonte determina os endereos dos receptores?duplicao

4: Camada de Rede

4: Camada de Rede4b-*Duplicao dentro da redeInundao: quando n recebe pacotes de broadcast, envia cpia para todos os vizinhosProblemas: ciclos e tempestades de broadcastInundao controlada: n somente faz broadcast do pacote se j no tiver feito antes com o mesmo pacoteN mantm registro sobre ids dos pacotes para os quais j fez broadcastOu adota o repasse pelo caminho inverso (Reverse Path Forwarding - RPF): s repassa pacote se chegou pelo caminho unicast mais curto at o remetentervores geradoras (spanning trees)Nenhum pacote redundante recebido por nenhum n

4: Camada de Rede

4: Camada de Rede4b-*rvore GeradoraPrimeiro construa uma rvore geradoraNs encaminham cpias somente ao longo da rvore geradora

4: Camada de Rede

4: Camada de Rede4b-*12345Construo passo-a-passo da rvore geradora(b) rvore geradora construdarvore Geradora: criaoN centralCada n envia mensagem de adeso ponto-a-ponto (unicast) endereadas ao n centralMensagem repassada at que chegue em um n j pertencente rvore geradora ou ao n central!

4: Camada de Rede

Problema de Roteamento MulticastMeta: achar uma rvore (ou rvores) conectando todos os roteadores com membros locais do grupo mcastrvore: nem todos os caminhos entre roteadores so usadosbaseada na fonte: rvore distinta de cada fonte para receptorescompartilhada: mesma rvore usada por todos os membros do gruporvore compartilhada

Abordagens para a construo de rvores mcastAbordagens:baseada na fonte: uma rvore por fontervores de caminhos mnimosenvio pelo caminho reversocompartilhada: grupo usa uma rvore nicarvore de custo mnimo (Steiner) rvore baseada em um centroprimeiro olharemos as abordagens bsicas, e depois protocolos especficos que adotam estas abordagens

rvore de Caminhos Mnimos

rvore de encaminhamento mcast: rvore composta pelos caminhos mnimos da fonte para todos os receptoresAlgoritmo de DijkstraR1R2R3R4R5R6R7roteador com membro dogrupo atreladoroteador sem membro dogrupo atreladoenlace usado p/ envio,i indica a ordem de adiodo enlace pelo algoritmoLEGENDAS: fonte

Repasse pelo Caminho Inversose (datagrama mcast recebido por um enlace de entrada no caminho mnimo de volta para a fonte)ento inunda o datagrama por todos os enlaces de sadaseno ignora o datagramaBaseia-se no conhecimento do roteador sobre caminhos mnimos unicast dele para a fontecada roteador tem um comportamento de envio simples:

Repasse pelo Caminho Inverso: exemploresultado uma rvore de caminho mnimo inverso especfica para a fonte- pode ser uma escolha ruim para enlaces assimtricosR1R2R3R4R5R6R7datagrama vai ser encaminhadoLEGENDAS: fontedatagrama no vai ser encaminhadoroteador com membro dogrupo atreladoroteador sem membro dogrupo atrelado

Envio pelo Caminho Reverso: podarvore de repasse contm sub-rvores sem nenhum membro do grupo multicastno h necessidade de enviar datagramas pelas sub-rvores mensagens de poda enviadas para trs pelo roteador sem nenhum membro do grupo pra frenteR1R2R3R4R5R6R7mensagem de podaLEGENDAS: fonteenlace com envio mcastPPProteador com membro dogrupo atreladoroteador sem membro dogrupo atrelado

rvore de Steinerrvore de Steiner: rvore de custo mnimo conectando todos os roteadores com membros locais do grupo mcastproblema NP-completoexistem excelentes heursticas no usada na prtica:complexidade computacionalnecessita informaes sobre a rede inteiramonoltica: recalculada sempre que um roteador precisa ser acrescentado/retirado

rvores baseadas em centrosrvore de envio nica compartilhada por todosum roteador eleito como centro da rvorepara juntar-se:roteador de fora envia msg-adeso unicast endereada ao roteador centralmsg-adeso processada pelos roteadores intermedirios e repassada para o centromsg-adeso ou chega a um ramo da rvore j existente para este centro, ou chega ao centrocaminho seguido por msg-adeso se torna novo ramo da rvore para este roteador

rvores baseadas em centros: exemploSuponha que R6 foi escolhido como centro:R1R2R3R4R5R6R7ordem em que as mensagens de juno so geradasLEGENDA2131roteador com membro dogrupo atreladoroteador sem membro dogrupo atrelado

Roteamento Multicast na Internet: DVMRPDVMRP: distance vector multicast routing protocol, RFC1075inundao e poda: envio pelo caminho inverso (RPF), rvore baseada na fontervore RPF baseada em tabelas de roteamento prprias do DVMRP, construdas por meio da comunicao entre roteadores DVMRPnada assume sobre o roteamento unicast subjacentedatagrama inicial para o grupo mcast inundado por todo lugar via RPFroteadores sem membros: mensagens de poda para cima

DVMRP: continuandoestado soft : roteador DVMRP esquece periodicamente (1 min.) que ramos esto podados: dados mcast novamente fluem pelos ramos no podadosroteador de baixo: refaz a poda ou continua a receber dadosroteadores podem rapidamente se enxertar na rvoreseguindo juno IGMP na folhaconsideraes finaiscomumente implementado em roteadores comerciaisroteamento Mbone feito atravs do DVMRP

TunelamentoQ: Como conectar ilhas de roteadores multicast em um oceano de roteadores unicast? datagrama mcast encapsulado dentro de um datagrama normal (sem endereo multicast)datagrama IP normal enviado atravs de um tnel via IP unicast regular para o roteador mcast receptorroteador mcast receptor desencapsula para obter datagrama mcastTopologia fsicaTopologia lgica

PIM: Protocol Independent Multicastno depende de nenhum algoritmo de roteamento unicast subjacente (trabalha com todos)Dois cenrios de distribuio multicast diferentes:Denso:Localizao dos membros do grupo de alta densidademaior disponibilidade de bandaEsparso:n de roteadores com membros do grupo pequeno em relao ao n total de roteadoresmembros do grupo amplamente dispersosmenor disponibilidade de banda

Conseqncias da Dicotomia Esparso-Denso: Densoparticipao dos roteadores nos grupos assumida at que os roteadores se podem explicitamenteconstruo da rvore mcast ditada pelos dados (e.x., RPF)uso da banda e processamento no roteador no participante do grupo perdulriosEsparso:sem participao at que os roteadores se juntem explicitamenteconstruo da rvore mcast ditada pelos receptores (e.x., baseada em centro)uso da banda e processamento no roteador no participante do grupo criteriosos

PIM- Modo Densoinundao com RPF e poda, similar ao DVMRP masProtocolo de roteamento unicast subjacente prov as informaes referentes ao datagrama chegando, necessrias ao RPFinundao menos complicada (menos eficiente) que a do DVMRP reduz a dependncia em relao ao algoritmo de roteamento subjacentepossui mecanismo no protocolo para que o roteador detecte que um n folha

PIM Modo Esparsoabordagem baseada em centroRoteador envia msg. de juno para o ponto de encontro (rendezvous point - RP)Roteadores intermedirios atualizam estado e encaminham msg. de junoaps se juntar via RP, roteador pode mudar p/ rvore baseada na fonteperformance melhorada: menos concentrao, caminhos menores

PIM Modo Esparsofonte(s):dados via rot. unicast para o RP, que os distribui ao longo da rvore com raiz no RPRP pode estender rvore mcast para cima at a fonteRP pode enviar msg. pare p/ fonte se no houver receptores atreladosningum est ouvindo!

4: Camada de Rede4b-*Camada de Rede: resumoPrxima parada: A camada de Enlace de Dados!O que ns cobrimos:Servios da camada de redeO que h dentro de um roteador?O Protocolo da Internet: IPAlgoritmos de roteamento: estado dos enlaces e vetor de distnciasroteamento hierrquicoprotocolos de roteamento Internet RIP, OSPF, BGPRoteamento broadcast e multicast

4: Camada de Rede

*********************************************************Notes:

3.3 Network Layer: Multicast Routing Algorithms 3-9*Notes:






1. See L. Wei and D. Estrin, A Comparison of multicast trees and algorithms, TR USC-CD-93-560, Dept. Computer Science, University of California, Sept 1993 for a comparison of heuristic approaches.


1. Its always nice to see a PhD dissertation with impact. The earliest discussion of center-based trees for multicast appears to be D. Wall, Mechanisms for Broadcast and Selective Broadcast, PhD dissertation, Stanford U., June 1980.


3.3 Network Layer: Multicast Routing Algorithms 3-18*Notes: D. Waitzman, S. Deering, C. Partridge, Distance Vector Multicast Routing Protocol, RFC 1075, Nov. 1988. The version of DVMRP in use today is considerably enhanced over the RFC1075 spec.A more up-to-date work-in-progress defines a version 3 of DVMRP: T. Pusateri, Distance Vector Multicast Routing Protocol, work-in-progress, draft-ietf-idmr-v3-05.ps

3.4 Network Layer: Internet Multicast Routing Algorithms 3-20*Notes:

1. See www.mbone.com/mbone/routers.html for a (slightly outdatet) list of multicast capable routers (supporting DVMPR as well as other protocols) from various vendors.2. ftp://parcftp.xerox.com/pub/net-research/ipmulti for circa 1996 public copy mrouted v3.8 of DVMRP routing software for various workstation routing platforms.

3.4 Network Layer: Internet Multicast Routing Algorithms 3-21*Notes: For a general discussion of IP encapsulation, see C. Perkins, IP Encapsulation within IP, RFC 2003, Oct. 1996.The book S. Bradner, A Mankin, Ipng: Internet protocol next generation, Addison Wesley, 1995 has a very nice discussion of tunnelingTunneling can also be used to connect islands of IPv6 capable routers in a sea IPv4 capable routers. The long term hope is that the sea evaporates leaving only lands of IPv6!


a very readable discussion of the PIM architecture is S. Deering, D. Estrin, D. Faranacci, V. Jacobson, C. Liu, L. Wei, The PIM Architecture for Wide Area Multicasting, IEEE/ACM Transactions on Networking, Vol. 4, No. 2, April 1996.D. Estrin et al, PIM-SM: Protocol Specification, RFC 2117, June 1997S. Deering et al, PIM Version 2, Dense Mode Specification, work in progress, draft-ietf-idmr-pim-dm-05.txt PIM is implemented in Cisco routers and has been deployed in UUnet as part of their streaming multimedia delivery effort. See S. LaPolla, IP Multicast makes headway among ISPs, PC Week On-Line, http://www.zdnet.com/pcweek/news/1006/06isp.html





3.4 Network Layer: Internet Multicast Routing Algorithms 3-29*

Documents

cap4b-2011