Camada rede

  • Published on
    21-Jun-2015

  • View
    5.686

  • Download
    8

Embed Size (px)

Transcript

<ul><li> 1. SumrioCamada de RedeQuestes de projeto Algoritmos de roteamento Algoritmos de controle de congestionamento Qualidade de servio Interligao de redes Camada de rede na InternetComutao de Pacotes store- Questes de Projetoand-forwardNo desenvolvimento de protocolos O ambiente de protocolos da camada de para a camada de rede, o projetistarede deve lidar com Comutao de pacotes store-and-forward Servios oferecidos camada de transporte Servios sem conexo ou orientados conexo Servios oferecidos camada Servios sem Conexo de transporte(Datagramas)Roteamento em uma sub-rede de Os servios so independentes da datagramas tecnologia de roteadores A camada de transporte deve ser isolada da topologia dos roteadores Endereamento uniforme independente do tamanho das redes Servios sem conexo e orientados conexo1 </li></ul><p> 2. Comparao entre redes de Servios Orientados Conexodatagramas e circuitos virtuaisRoteamento em uma sub-rede decircuitos virtuais5-4 Algoritmos de Roteamento Algoritmos de Roteamento Software responsvel pela escolha da linhaConflito entre justia e otimizao de sada Criao de tabelas de encaminhamento ou repasse Devem obedecer algumas propriedades Simplicidade Robustez Estabilidade Justia Otimizao Algoritmos de Roteamento Algoritmos de RoteamentoOs algoritmos de roteamento podemPrincpio da otimizao serSe o roteador J estiver no caminho timo entre Ie K, ento o caminho timo entre J e K estar Estticosna mesma rotaEscolha das rotas feita offline e enviadapara os roteadoresConsequnciaConjunto de rotas timas de todas as origens Dinmicos (adaptativos)para um determinado destino formam umaEscolha das rotas feita com base na rvore com raiz no destinotopologia e no trfego da redervore de escoamentoAssimilam mudanas que possam rvore no contm loopseventualmente ocorrer 2 3. Princpio da otimizao Algoritmo de Dijkstra (a) Uma sub-rede (b) Uma rvore deescoamento para o roteador B Algoritmo pelo caminho mais curto Curto aqui se refere ao caminho de menor custo O custo pode englobar variveis como o nmero de saltos, a distncia geogrfica, o de menor retardo, etc. Algoritmo de Dijkstra Algoritmo de Dijkstra Topologia de rede e custo dos enlaces so conhecidos por1 Inicializao: todos os ns2 N = {u} Computa caminhos de menor custo de um n (fonte) para 3 para todos os ns v todos os outros ns 4se v adjacente a uFornece uma tabela de roteamento para aquele n5 ento D(v) = c(u,v) Convergncia: aps k iteraes, conhece o caminho de6 seno D(v) = menor custo para k destinos 7 Notao:8 LoopC(i,j): custo do enlace do n i ao n j. Custo infinito se no 9 ache w no em N tal que D(w) um mnimohouver ligao entre i e j 10 acrescente w a ND(v): valor atual do custo do caminho da fonte ao destino V11 atualize D(v) para todo v adjacente a w e no em N:P(v): n predecessor ao longo do caminho da fonte ao n v, isto12 D(v) = min( D(v), D(w) + c(w,v) ), antes do vN: conjunto de ns cujo caminho de menor custo 13 /* novo custo para v ou o custo anterior para v ou o menordefinitivamente conhecido14 custo de caminho conhecido para w mais o custo de w a v */ 15 at que todos os ns estejam em N Algoritmo de Dijkstra Algoritmo de InundaoTcnica usada em protocolos de roteamento por difuso (broadcast) O roteador envia uma cpia do pacote recebido para todas as suas linhas de sada com exceo daquela em que o pacote chegou Problema com loops Nmeros de sequncia podem ser necessrios 3 4. Roteamento com vetor de Roteamento com vetor dedistncia distnciaUm n recebe informao de seus Equao de Bellman-Ford (programao vizinhos, realiza clculos e repassa odinmica) resultado para seus vizinhosDefine-se Algoritmo distribudo e assncronodx(y) = custo do caminho de menor custo de x para y Algoritmo usado originalmente na ARPANET e na Internet (RIP) Ento dx(y) = min {c(x,v) + dv(y) } Foi substitudo em razo da convergncia lentaEm que min calculado sobre todos os vizinhos de xRoteamento com vetor de Roteamento com vetor dedistncia distncia Claramente, dv(z) = 5, dx(z) = 3, Dx(y) = estimativa do menor custo de x paradw(z) = 3 yA equao B-F diz que: Vetor de distncia: Dx = [Dx(y): y N ] du(z) = min { c(u,v) + dv(z), N sendo a vizinhana de x c(u,x) + dx(z), O n x conhece o custo para cada vizinho v: c(u,w) + dw(z) }c(x,v)= min {2 + 5, 1 + 3,O n x mantm Dx = [Dx(y): y N ] 5 + 3} = 4O n x tambm mantm os vetores de distncia de seus vizinhos Para cada vizinho v, x mantm Dv = [Dv(y): y N O n que atinge o mnimo o prximo salto no caminho mais curto ]Roteamento com vetor de Roteamento com vetor dedistncia distnciaPara cada n x:1 Inicializao:2Para todos os destinos y em N:Idia bsica:3 Dx(y) = c(x,y) /* se y no um vizinho ento c(x,y) = /*4Para cada vizinho w Cada n envia periodicamente sua prpria5 Dw(y) = para todos os destinos y em Nestimativa de vetor de distncia aos vizinhos6Para cada vizinho w7 Envia um vetor de distncias (DV) Dx = [Dx(y): y N ] para wQuando o n x recebe nova estimativa de DV do8vizinho, ele atualiza seu prprio DV usando a9 loop equao B-F:10 Espera (at que ocorra uma mudana no custo do enlace ao vizinho11 w ou at a recepo de um vetor de distncias do vizinho w)Dx(y) = minv{c(x,v) + Dv(y)} para cada n y N12 Ao menos em condies naturais, a estimativa13 Para cada y em N:14Dx(y) = min v {c(x,y) + Dv(y)} Dx(y) converge para o menor custo atual dx(y)1516 Se Dx(y) mudou para algum destino y17Envia um DV Dx = [Dx(y): y N ] para todos os vizinhos18 para sempre4 5. Roteamento com vetor de Roteamento com vetor dedistncia distncia Dx(y) = min{c(x,y) + Dy(y), c(x,z) + Dz(y)}= min{2+0 , 7+1} = 2Iterativo, assncrono: cadaCada n:iterao local causada por: Dx(z) = min{c(x,y) +Dy(z), c(x,z) + Dz(z)}espera por (mudana no custo Mudana no custo do enlacedo enlace local na mensagem do= min{2+1 , 7+0} = 3 local vizinho) Mensagem de atualizao DVdo vizinhorecalcula estimativasDistribudo: Cada n notifica os vizinhosse o DV para qualquer destino apenas quando seu DV mudar mudou, notifica os vizinhos Os vizinhos ento notificam seus vizinhos, se necessrioRoteamento com vetor de Roteamento com vetor dedistncia distnciaMudanas no custo do enlace: Mudanas no custo do enlace: Boas notcias viajam rpido (reduo no custo) N detecta mudana no custo do Ms notcias viajam devagar problema da contagem ao infinito! enlace local 44 iteraes antes de o algoritmo estabilizar Atualiza informaes de roteamento,Reverso envenenada: recalcula o vetor de distnciaTentativa de solucionar esse problema Se o DV muda, notifica vizinhosNo funciona bem no caso geralNo tempo t0, y detecta a mudana no custo do enlace, atualiza seu DV e informa seus vizinhos. No tempo t1, z recebe a atualizao de y e atualiza sua tabela. Ele calcula o menor custo novo para x e envia seu DV para os vizinhos. No tempo t2, y recebe a atualizao de z e atualiza sua tabela de distncia. O menor custo de y no muda e ento y no envia nenhuma mensagem para z. boas notcias viajam depressaRoteamento por Estado deRoteamento por Estado deEnlaceEnlaceAmplamente utilizadoConhecendo os vizinhosEnvio de um pacote HELLO especial em cada linha pontoCada roteador deve fazer o seguinte a pontoDescobrir seus vizinhos e aprender seus Roteador do outro lado envia uma respostaendereos de rede Medio do custo da linhaMedir o retardo ou o custo at cada um de seusEnviar um pacote ECHOvizinhosMede-se o tempo e divide-se por doisCriar um pacote que informe tudo o que elePode-se levar em conta ou no o retardo das filas nosacabou de aprenderroteadores No primeiro caso, o timer iniciado quando o pacote ECHOEnviar esse pacote a outros roteadores enfileiradoCalcular o caminho mais curto at cada um dosNo segundo caso, o timer iniciado quando o pacote ECHOoutros roteadores (Dijkstra) atinge o incio da fila 5 6. Roteamento por Estado de Roteamento por Estado de Enlace Enlace Se o roteamento levar em conta o atrasoda fila, as tabelas de roteamento podem oscilar entre as linhas CF e EI (a) Sub-rede (b) Pacotes de estado de enlace para essa sub-rede Nmeros de seqncia permitem descartar pacotes velhos ou repetidos O campo idade permite que o roteador descarte informaes antigas para os casos em que o roteador fique inativo, ou ocorra um problema com a seqncia. Roteamento por Estado de Enlace Roteamento HierrquicoBuffer de pacotes para o roteador BAs tabelas de roteamento se tornammaiores a medida que o nmero deroteadores aumentaA soluo segmentar os roteadoresem regies Tabelas mais simples Solues de roteamento podem no ser mais timasRoteamento para Hosts Roteamento Hierrquico MveisCenrio tpico6 7. Roteamento para HostsRoteamento em Redes AdMveis Hoc Roteamento de pacotes para usuriosRoteadores mveisVeculos militares em um campo de batalha semmveis. nenhuma infra-estruturaUma frota de navios no mar se movendo aomesmo tempoTrabalhos em calamidades com infra-estruturadestrudaGrupo de pessoas com notebooks usando o padro802.11 Topologia muda constantemente SoluoAlgoritmo AODV Ad hoc On-demand Distance Vector.S utilizado quando se necessita transmitir algoRoteamento em Redes Ad Roteamento em Redes AdHoc (Descoberta da rota) Hoc (Descoberta da rota)(a)Alcance de difuso para A. (b)Depois de B e D receberem Formato de um pacote ROUTE REQUEST. a difuso de A. (c)Depois de C, F e G receberem a difuso de A. (d) Depois de E, H e I receberem a difuso de A. Os ns sombreados so novos destinatrios. As setas mostram as rotas inversas possveis.Roteamento em Redes Ad Roteamento em Redes AdHoc (Descoberta da rota) Hoc (Manuteno da rota) (a) Tabela de roteamento de D antes de G ficar inativo(b) O grafo depois que G fica inativo. Formato de um pacote ROUTE REPLY. 7 8. Algoritmos de Controle de Algoritmos de Controle de CongestionamentoCongestionamentoQuando h mais pacotes do que os roteadores podem processar em uma determinada regio de uma sub-rede, o desempenho cai Congestionamento Pacotes podem ser descartados ou apresentar um retardo acima do permitido Algoritmos de Controle de Princpios de Controle de CongestionamentoCongestionamentoCausas do congestionamentoSolues podem ser classificadas em Processadores lentosMalha aberta Enlaces de sada com banda insuficiente Decises so tomadas sem levar em conta o estado atual da rede Controle de congestionamento Tcnicas usadas para que a sub-rede possa Malha fechada garantir que o trfego seja encaminhado Decises so tomadas com base na realimentao de algum parmetro como: a Controle de fluxo percentagem de pacotes descartados, a Se refere a enlaces ponto a ponto mdia do comprimento das filas, o nmero de pacotes que atingem o timeout, etc. Compatibilizao de velocidades Princpios de Controle de Polticas de Preveno de CongestionamentoCongestionamento Com a realimentao, a ao de controle de congestionamento dividida em Monitorar o sistema para detectar quando e onde ocorre congestionamento Enviar essas informaes para lugares onde alguma providncia possa ser tomada Ajustar a operao do sistema para corrigir o problema 8 9. Controle de CongestionamentoControle de Congestionamento em Redes de Circuitos Virtuaisem Redes de Circuitos VirtuaisControle de admisso Quando houver sinal de congestionamento, nenhum outro circuito virtual ser estabelecido Idia empregada no sistema telefnico Uma modificao dessa idia criar novos circuitos virtuais evitando reas problemticas Outra possibilidade negociar uma certa(a)Rede Congestionada qualidade de servio no estabelecimento do circuito virtual(b)Rede redesenhada que elimina ocongestionamento Controle de CongestionamentoControle de Congestionamento em Redes de Datagramasem Redes de DatagramasOs roteadores monitoram as suasBit de advertnciaBit de advertncia colocado nos pacotes de linhas de sada e associam algunsconfirmao parmetros de desempenho a uma A origem das transmisses faz uma mdia e varivel de controle reduz a taxa de transmisso se necessrio Valor acima de um limiar indica que h Pacotes reguladoresPacote regulador enviado pelo roteador ao congestionamento host de origem Detectado o congestionamento, vrias A cada pacote regulador recebido o host reduza sua taxa em x% aes podem ser tomadas Controle de CongestionamentoPacotes em Redes de DatagramasreguladoresPacotes reguladores salto a salto (a) Um pacote Pacotes reguladores do roteadorregulador que afeta congestionado ao host de origem podem demorar para chegarapenas a origem Nesse tempo o host continua mandando(b) Um pacote dadosregulador que afeta A reduo da taxa em pontoscada salto por onde intermedirios alivia o destino final mais rapidamentepassa.9 10. Controle de CongestionamentoControle de Congestionamento em Redes de Datagramasem Redes de DatagramasEscoamento de carga Pacotes devem ser descartados quando os roteadores no puderem lidar com eles Esquemas de prioridade podem ser usados para um descarte mais inteligente Deteco aleatria prematura Roteadores descartam pacotes aleatoriamente antes da linha ficar congestionada Controle de Jitter (Flutuao) (a) Jitter alto(b) Jitter baixo Qualidade de ServioQualidade de Servio Rigidez dos requisitos de qualidade de servio Tcnicas para alcanar qualidade de servio SuperdimensionamentoSoluo dispendiosa Armazenamento em buffersPermite lidar com o jitter Moldagem de trfegoTrfego uniforme Qualidade de ServioQualidade de Servio O fluxo de sada suavizado por meioAlgoritmo do balde furado do armazenamento em buffers Pacotes so armazenados at o balde encher A sada regulada pelo furo no balde Algoritmo do balde de smbolos O balde armazena smbolos Para um pacote ser transmitido, necessrio um smbolo do balde10 11. Algoritmo do balde de Algoritmo do balde furado smbolos 5-34 Qualidade de ServioInterligao de Redes Programao de pacotesExiste uma quantidade abundante de tiposO objetivo garantir justia quando ode redesroteador lida com vrios fluxos TCP/IP, redes ATM, LANs com os protocolosNovell NCP/IPX, etc.Algoritmo do enfileiramento justoPor questes de custos, prefervel muitasvezes trabalhar com diversos tipos de redesdo que uniformizarAs tecnologias so muitas vezes distintas eos servios oferecidos so incompatveis Interligao de Redes Interligao de RedesDiferenas entre redes11 12. Interligao de Redes Interligao de RedesInterligao atravs de circuitos virtuais (a) Duas redes Ethernet conectadas por um switch. concatenados (b) Duas redes Ethernet conectadas por roteadores.Interligao de Redes Interligao de RedesInterligao de redes sem conexesTunelamentoInterligao de Redes Roteamento Inter-Redes Tunelamento (a) An internetwork. (b) A graph of the internetwork. 12 13. FragmentaoCamada de Rede da Internet(a) Fragmentao transparente. (b)Fragmentao no transparente. A Internet uma coleo de redes interconectadas Camada de Rede da InternetProtocolo IPProtocolo IPO Cabealho IPv4. Ponto de unio da Internet Todos os computadores interligados implementam este protocolo Atualmente ainda predomina a verso 4 (ipv4) A verso 6 (ipv6) est substituindo o ipv4 Maior capacidade de endereamento Verses atuais dos Sistemas Operacionais j implementam o ipv6 Protocolo IPProtocolo IPPossibilidades de uso do campo Endereos IP options...</p>