PublicouMariana Carlos Alterado mais de 5 anos atrás
Step 1 2 3 4 5 N' u ux uxy uxyv uxyvw uxyvwz D(v),p(v) 2,u D(w),p(w) 5,u 4,x 3,y D(x),p(x) 1,u D(y),p(y) ∞ 2,x D(z),p(z) ∞ 4,y u y x w v z 2 1 3 5 4: Camada de Rede
11 Algoritmo de Dijkstra, discussão
Complexidade algoritmica: n nós a cada iteração: precisa checar todos nós, w, não em N' n*(n+1)/2 comparações => O(n2) implementações mais eficientes possíveis: O(nlogn) Oscilações possíveis: p.ex., custo do enlace = carga do tráfego carregado A A D C B 2+e 1+e 1 A A D C B 2+e e 1+e 1 1 1+e 2+e D B D B e 1 C 1+e C 1 1 e … recalcula rotas … recalcula … recalcula inicialmente 4: Camada de Rede
12 Capítulo 4: Camada de Rede
13 Algoritmo Vetor de Distâncias
14 Exemplo com Bellman-Ford
15 Algoritmo Vetor de Distâncias
16 Algoritmo Vetor de Distâncias (4)
17 Algoritmo Vetor de Distâncias (5)
18 z y x Dx(z) = min{c(x,y) + Dy(z), c(x,z) + Dz(z)} = min{2+1 , 7+0} = 3
Dx(y) = min{c(x,y) + Dy(y), c(x,z) + Dz(y)} = min{2+0 , 7+1} = 2 tabela nó x x y z x y z ∞ origem custo para custo para custo para x y z x y z x x origem y origem y z z tabela nó y custo para custo para custo para x z 1 2 7 y x y z x y z x y z x ∞ ∞ ∞ x x origem origem y y origem y z z ∞ ∞ ∞ z tabela nó z custo para custo para custo para x y z x y z x y z x x x ∞ ∞ ∞ origem origem origem y y y ∞ ∞ ∞ z z z 7 1 tempo 4: Camada de Rede
19 Vetor de Distâncias: mudança no custo dos enlaces
20 Vetor de Distâncias: mudança no custo dos enlaces
21 Comparação dos algoritmos EE e VD
22 Capítulo 4: Camada de Rede
23 Roteamento Hierárquico
24 Roteamento Hierárquico
25 SAs interconectados 3b 1d 3a 1c 2a SA3 SA1 SA2 1a 2c 2b 1b Algoritmo de roteamento intra-AS Tabela de encaminhamento 3c Tab. de encaminhamento é configurada pelos algoritmos intra-SA e inter-SA Intra-SA define entradas p/ dest. internos Inter-SA e Intra-SA define entradas p/ dest. externos 4: Camada de Rede
26 Tarefas do roteamento inter-SA
27 Exemplo: definindo a tabela de encaminhamento no roteador 1d
28 Exemplo: escolhendo entre múltiplos SAs
30 Roteamento Intra-SA Também conhecidos como Interior Gateway Protocols (IGP) Os protocolos de roteamento Intra-SA mais comuns são: RIP: Routing Information Protocol OSPF: Open Shortest Path First IGRP: Interior Gateway Routing Protocol (proprietário da Cisco) 4: Camada de Rede
32 RIP (Routing Information Protocol)
33 Anúncios RIP Vetores de distâncias: trocados a cada 30 seg via Mensagem de Resposta (também chamada de anúncio) Cada anúncio: rotas para até 25 redes destino dentro do SA 4: Camada de Rede
34 Exemplo RIP z w ... x y A D B C y B 2 z B 7 x -- 1
35 Exemplo RIP z w ... x y A D B C y B 2 z B A 7 5 x -- 1 Anúncios de
36 RIP: Falha e Recuperação de Enlaces
37 RIP: Processamento de tabelas
38 Capítulo 4: Camada de Rede
39 OSPF (Open Shortest Path First)
40 OSPF: características "avançadas" (não existentes no RIP)
41 OSPF Hierárquico 4: Camada de Rede
42 OSPF Hierárquico Hierarquia de dois níveis: área local, backbone.
43 Capítulo 4: Camada de Rede
44 Roteamento inter-SA na Internet: BGP
45 Fundamentos do BGP Par de roteadores (pares BGP) trocam info. de roteamento através de conexões TCP semi-permanentes TCP: sessões BGP Note que sessões BGP não correspondem a enlaces físicos. Quando um SA2 anuncia um prefixo para SA1, SA2 está prometendo que vai enviar àquele prefixo quaisquer datagramas destinados ao mesmo. SA2 pode agregar prefixos nos seus anúncios 3b 1d 3a 1c 2a SA3 SA1 SA2 1a 2c 2b 1b 3c eBGP session iBGP session 4: Camada de Rede
46 Distribuindo informação de alcançabilidade
47 Atributos de caminho & Rotas BGP
48 Seleção de rota do BGP Roteador pode aprender sobre mais de 1 rota para algum prefixo. Ele deve selecionar a rota. Regras de eliminação: Valor do atributo preferência local associado à rota: decisão política Menor AS-PATH Roteador NEXT-HOP mais próximo: roteamento batata quente Critérios adicionais 4: Camada de Rede
49 Mensagens BGP Mensagens BGP trocadas usando TCP. Mensagens BGP:
50 Políticas de roteamento BGP
51 Políticas de roteamento BGP (2)
52 Por quê há diferenças entre roteamento Intra- e Inter-SA?
54 Roteamento Broadcast Envia pacotes de uma para todos os outros nós Duplicação na fonte é ineficiente: duplicação criação/transmissão duplicada R1 R1 duplicação R2 R2 R3 R4 R3 R4 duplicação na fonte duplicação dentro da rede Duplicação na fonte: como a fonte determina os endereços dos receptores 4: Camada de Rede
55 Duplicação dentro da rede
56 Árvore Geradora Primeiro construa uma árvore geradora
57 Árvore Geradora: criação
58 Roteamento Multicast: definição do problema
59 Abordagens para a construção de árvores mcast
60 Árvore de Caminhos Mínimos
61 Envio pelo Caminho Reverso
62 Envio pelo Caminho Reverso: exemplo
63 Envio pelo Caminho Reverso: poda
64 Árvore de Steiner Árvore de Steiner: árvore de custo mínimo conectando todos os roteadores com membros locais do grupo mcast problema NP-completo existem excelentes heurísticas não é usada na prática: complexidade computacional necessita informações sobre a rede inteira monolítica: recalculada sempre que um roteador precisa ser acrescentado/retirado Notes: 1. See L. Wei and D. Estrin, "A Comparison of multicast trees and algorithms," TR USC-CD , Dept. Computer Science, University of California, Sept 1993 for a comparison of heuristic approaches. 3.3 Network Layer: Multicast Routing Algorithms
65 Árvores baseadas em centros
66 Árvores baseadas em centros: exemplo
67 Roteamento Multicast na Internet: DVMRP
68 DVMRP: continuando… estado soft : roteador DVMRP "esquece" periodicamente (1 min.) que ramos estão podados: dados mcast novamente fluem pelos ramos não podados roteador de baixo: refaz a poda ou continua a receber dados roteadores podem rapidamente se enxertar na árvore seguindo junção IGMP na folha considerações finais comumente implementado em roteadores comerciais roteamento Mbone feito através do DVMRP Notes: 1. See 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
69 Tunelamento Q: Como conectar "ilhas" de roteadores multicast em um "oceano" de roteadores unicast? Topologia física Topologia lógica datagrama mcast encapsulado dentro de um datagrama "normal" (sem endereço multicast) datagrama IP normal enviado através de um "túnel" via IP unicast regular para o roteador mcast receptor roteador mcast receptor desencapsula para obter datagrama mcast Notes: For a general discussion of IP encapsulation, see C. Perkins, "IP Encapsulation within IP," RFC 2003, Oct The book S. Bradner, A Mankin, "Ipng: Internet protocol next generation," Addison Wesley, 1995 has a very nice discussion of tunneling Tunneling 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! 3.4 Network Layer: Internet Multicast Routing Algorithms