Camada De Rede Objetivos Sumário: - ppt carregar
PublicouHeloísa Chao Alterado mais de 4 anos atrás
Apresentação em tema: "Camada De Rede Objetivos Sumário:"— Transcrição da apresentação:
1 Camada De Rede Objetivos Sumário:
Explicar as funções da camada de rede Roteamento (esc. Caminho) Escalabilidade Como funciona um roteador Tópicos avançados: ipv6, multicast Instanciação e implementação na intenet Sumário: Serviços da camada de rede Routeamento: seleção de rotas Roteamento hierárquico Ip Protocolos de roteamento da internet Intra-domain Inter-domain Como funciona um roteador IP Ipv6 Roteamento multicast
"A ligação entre a origem e o destino emula uma ligação telefônica" Orientado ao desempenho A rede controla a conexão entre a origem e o destino Estabelecimento da conexão deve preceder o envio de dados. Liberação da conexão após os dados. Cada pacote transporta um identificador do CV, não transporta o endereço completo do destino Cada roteador na rota mantém informação de estado para conexão que passa por ele. A conexão de camada de transporte envolve apenas os sistemas finais A banda passante e os recursos do roteador podem ser alocado por VC Controle de Qualidade de Serviço por VC
Parâmetros Garantidos Arquitetura de Rede Internet ATM Modelo de Serviço melhor esforço CBR VBR ABR UBR Realim. de Congestão não (examina perdas) não há congestão sim não Banda não taxa constante garantida mínimo garantido Perda não sim Ordem não sim Tempo não sim Novos serviços na Internet: Intserv, Diffserv
8 Datagrama versus Circuito Virtual
9 Protocolo de Roteamento
B F 2 1 3 5 OBJ: determinar "bons" caminhos (seqüência de roteadores) através da rede da fonte ao destino. Algoritmos de roteamento são descritos por grafos: Nós do gráfico são roteadores Arestas do gráfico são enlaces Custo do enlace: atraso, preço ou nível de congestão "bons" caminhos: tipicamente corresponde aos caminhos de menor custo caminhos redundantes
10 Classificação dos Algoritmos de Roteamento
Informação global ou descentralizada Global: Todos os roteadores tem informações completas da topologia e do custos dos enlaces algoritmos "Link state" Descentralizada: Roteadores só conhecem informações sobre seus vizinhos e os enlaces para eles Processo de computação interativo, troca de informações com os vizinhos algoritmos "Distance vector" Estático ou Dinâmico? Estático: As rotas mudam lentamente ao longo do tempo Dinâmico: As rotas mudam mais rapidamente Atualizações periódicas Podem responder a mudanças no custo dos enlaces
11 Algoritmo Link-state Algoritmo de Dijkstra Notação:
12 Algoritmo de Dijsktra's
1 Inicialização: 2 N = {A} 3 para todos os nós v se v é adjacente a A então D(v) = c(A,v) senão D(v) = infty 7 8 Loop 9 ache w não em N tal que D(w) é um mínimo 10 acrescente w a N 11 atualize D(v) para todo v adjacente a w e não em N: D(v) = min( D(v), D(w) + c(w,v) ) 13 /* novo custo para v é ou o custo anterior para v ou o menor custo de caminho conhecido para w mais o custo de w a v */ 15 até que todos os nós estejam em N
13 Exemplo: Algoritmo de Dijkstra
14 Discussão do Algoritmo de Dijkstra
Complexidade do Algoritmo: n nós Cada iteração: precisa verificar todos os nós w, que não estão em N Complexidade: N*(n+1)/2 comparações: o(n**2) Implementações mais eficientes: o(nlogn) Oscilações possíveis: E.G., custo do enlace = total de tráfego transportado 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 roteamento … recalcula … recalcula inicial
15 Algoritmo "Distance Vector"
Iterativo: Continua até que os nós não troquem mais informações. Self-terminating: Não há sinal de parada Assíncrono: Os nós não precisam trocar informações simultaneamente! Distribuído: Cada nós se comunica apenas com os seus vizinhos, diretamente conectados Estrutura de Dados da Tabela de Distância Cada nó tem sua própria tabela Linha para cada possível destino Coluna para cada roteador vizinho Exemple: no nó X, para destino Y via vizinho Z: D (Y,Z) X distância de X to Y, via Z como prox. salto c(X,Z) + min {D (Y,w)} Z w =
16 Exemplo de Tabela de Distância
7 8 1 2 D () A B C D 1 7 6 4 14 8 9 11 5 2 E custo via nó vizinho destino D (C,D) E c(E,D) + min {D (C,w)} D w = 2+2 = 4 D (A,D) E c(E,D) + min {D (A,w)} D w = 2+3 = 5 loop! D (A,B) E c(E,B) + min {D (A,w)} B w = 8+6 = 14 loop!
17 A Tabela de Distâncias Gera a Tabela de Roteamento
18 Roteamento Vetor-Distância: Resumo
19 Algoritmo Vetor-Distância:
Para todos os nós, X: 1 Inicialização: 2 para todos os nós adjacentes v: D (*,v) = infinito /* o operador * significa "para todas as colunas" */ D (v,v) = c(X,v) 5 para todos os destinos, y envia min D (y,w) para cada vizinho /* w sobre todos vizinhos de X*/ X X X w
20 Algoritmo Vetor-Distância (Cont.):
8 loop 9 wait (até ocorrer uma mudança no custo do enlace para vizinho V ou até receber atualização do vizinho V) 11 12 if (c(X,V) muda por d) /* muda o custo para todos os destinos via vizinho v por d */ /* nota: d pode ser positivo ou negativo */ para todos os destinos y: D (y,V) = D (y,V) + d 16 17 else if (atualização recebida de V sobre destino Y) /* caminho mais curto de V para algum Y mudou */ /* V enviou um novo valor para seu min DV(Y,w) */ /* chame este novo valor recebido "newval" */ para o único destino y: D (Y,V) = c(X,V) + newval 22 23 if nós temos um novo min D (Y,w) para algum destino Y envie novo valor de min D (Y,w) para todos os vizinhos 25 26 forever X X w X X w X w
21 Exemplo: algoritmo vetor-distância
Z 1 2 7 Y
Z 1 2 7 Y D (Y,Z) X c(X,Z) + min {D (Y,w)} w = 7+1 = 8 Z D (Z,Y) X c(X,Y) + min {D (Z,w)} w = 2+1 = 3 Y
23 Vetor-Distância: Mudança no custo do enlace
nó detecta que o custo do enlace local mudou atualiza tabela de distâncias (linha 15) se o custo do caminho de menor custo mudou, notifica vizinhos (linhas 23 e 24) X Z 1 4 50 Y algoritmo termina "boas notícias viajam depressa"
24 Vetor Distância: Mudança no custo do enlace
más notícias viajam devagar - problema da contagem ao infinito X Z 1 4 50 Y 60 algoritmo continua!
25 Vetor Distância: Divisão Horizontal de Inversão Envenenada (Poisoned Reverse)
Se Z roteia através de Y para chegar a X : Z diz a Y que sua (de Z) distância para X é infinita (assim Y não roteará para X via Z) será que isso resolve completamente o problema da contagem ao infinito? X Z 1 4 50 Y 60 algoritmo termina
26 Comparação dos Algoritmos LS e VD
Problemas do mundo real roteadores não são todos idênticos as redes não são "flat" na prática Escala: com 50 milhões de destinos: Não é possível armazenar todos os destinos numa única tabela de rotas! As mudanças na tabela de rotas irão congestionar os enlaces! Autonomia Administrativa Internet = rede de redes Cada administração de rede pode querer controlar o roteamento na sua própria rede
roteadores de borda Agrega roteadores em regiões, "sistemas autônomos " (AS) Roteadores no mesmo AS rodam o mesmo protocolo de roteamento Protocolo de roteamento "Intra-AS" Roteadores em diferentes AS podem rodar diferentes protocolos de roteamento Roteadores de interface de um AS Rodam protocolos de roteamento intra-AS com os outros roteadores do AS Também responsáveis por enviar mensagens para fora do AS Rodam protocolo de roteamento inter-AS com outros rotea-dores de borda
29 Roteamento Intra-as and Inter-as
30 Roteamento Intra-AS e Inter-AS
31 A camada de rede da Internet
parte de rede (bits mais significativos) parte de Host part (bits menos significativos) O que é uma rede? (na prespectiva do endereço) Interfaces de dispositivos com a mesma parte de rede no endereço IP Podem fisicamente se comunicar sem o auxílio de um rotedor LAN rede consistindo de de 3 redes IP (para endereços IP começando com 223, os primeiros 24 bits são o endereço de rede )
34 Endereçamento IP Como encontrar as redes
35 Endereços IP endereçamento "class-full": class A B C D 32 bits rede
37 Como obter um endereço IP
Rede (porção de rede) Obter uma parte do espaço de endereços do seu ISP: bloco do ISP /20 Organização /23 Organização /23 Organização /23 … … …. Organização /23
40 Roteamento Hierárquico:rotas mais específicas
41 Como obter um endereço IP...
42 Levando um Datagrama da Fonte ao Destino
tabela de roteamento em A Rede destino próx. roteador Núm. saltos datagrama IP: outros campos endereço IP origem IP destino dados A B E os endereços do datagrama não mudam ao viajar da fonte ao destino
outros campos Rede destino Próx. roteador Núm. saltos dados Começando em A, levar datagrama IP para B: examine endereço de rede de B descobre que B está na mesma rede de A camada de enlace envia datagrama diretamente para B num quadro da camada de enlace Se necessário descobre endereço físico de B B e A são diretamente conectados A B E
outros campos Rede destino Próx. roteador Núm. saltos dados Começando em A, dest. E: examina endereço de rede de E E está num rede diferente A, E não estão diretamente conectados tabela de roteamento: próximo roteador para E é encontra endereço físico de e envia o datagrama num quadro de enlace datagrama chega em continua….. A B E
Próx. roteador Núm. saltos Endereço Interface outro campos Rede destino dados Chegando em , destino examina endereço de rede de E E está na mesma rede da interface do roteador roteador e E estão diretamente ligados descobre endereço físico de e envia o datagrama num quadro da camada de enlace datagrama chega em !!! (ufa!) A B E