Keep in mind that this is not a public wiki for arbitrary use.

You can use it for initial testing, but please, if you are finished with testing, remove your content again.

If you need a wiki, please contact me via email.

-- ThomasWaldmann 2003-09-02 15:09:19

Hi Thomas, I send e-mail for you... tw-public@gmx.de this e-mail is correct?

-- FabianoRighetti

Yes, will answer soon. -- ThomasWaldmann 2003-09-04 14:41:06

Ok! Thanks.

-- FabianoRighetti 2025-01-21 00:42:53

Redes de Computadores e Sistemas Distribuidos - Terceiro Bimestre

Switching de Enlace

• Pontes não trocam o endereço da fonte (source address).

• Pontes são P&P (Plug and Play), realizando aprendizado automático.

• Inicialmente a tabela de ponte está vazia (empty).
• Quando chega um quadro (frame) e o endereço de destino não está na tabela, repassa cópias do quadro para todos os buffers de saída (CSMA/CD).
• Para cada quadro recebido, a ponte armazena:
  • "Ethernet Address" do campo endereço fonte (source address).
  • Interface origem do quadro.
  • Horário.
  • Quando estiver na tabela, repassa.
  • Registros na tabela podem ser apagados quando "envelhecerem".
• Pontes aplicam o protocolo "Spanning Tree".
  • Trajetos múltiplos entre segmentos de LAN melhoram a tolerância a falhas, mas criam quadros duplicados.
  • O algoritmo do "Spanning Tree" remove loop, gerando um subconjunto da topologia original.
  • Caso interfaces desconectadas falhem, o ST pode ser rodado para habilitá-las.

  	Equipamento
  	Hub	Ponte	Roteador	Comutadores
  Isolamento de Tráfego	não	sim	sim	sim
  Plug & Play	sim	sim	não	sim
  Roteamento Ótimo	não	não	sim	não
  Comutação Acelerada	sim	não	não	sim

LANs IEEE 802.11

• LANs Wireless
• IEEE 802.11 define
  • Camada Física
  • Camada MAC
• Três diferentes camadas físicas, uma para cada frequência
  • Velocidade entre 1Mbps e 2Mbps
  ==== Componentes ====
  • ===== BSS =====

    • Basic Service Set: Célula composta por uma ou mais estações wireless e um Access Point (AP). As estações fixas ou móveis comunicam-se com o AP através do MAC IEEE 802.11. Vários APs podem conectar-se e formam um DS (Distributed System).

      Várias estações podem conectar-se e formar uma rede ad hoc, sem AP central, cujo interesse vem crescendo devido a proliferação de portáteis, como palms.

    ===== Acesso ao Meio =====

    • O MAC IEEE 802.11 coordena o acesso ao meio compartilhado -> rádio freqüência. O protocolo empregrado é o CSMA/CD (Carrier Sense Multiple Access/Colision Avoidance) com prevenção de colisão. A estação que deseja transmitir monitora o nível de energia da frequência de rádio, passando essa informação ao MAC. Caso a ociosidade detectada seja igual ou superior ao DIFS (Distribuited Inter Frame Space) a estação transmite o quadro. A estação destinatária ao receber o quadro aguarda um tempo SIFS (Short Inter Frame Space) e devolve um reconhecimento ao remetente. E quando o canal (meio) está ocupado:

      • Aguarda uma ociosidade do canal maior ou igual ao DIFS.

      • Cálcula backoff adicional.

      • Faz contagem regressiva enquanto ouve o meio, quando zerar transmite.
      • Não implementa detecção de colisão.
      • O frame 802.11 possui um campo de duração, indicando a duração de transmissão de forma explicita.

      • As outras estações devem aguardar esse tempo mínimo => NAV (Network Allocation Vector) adiando o acesso, evitando colisões.

      • Também implementa o quadro RTS (Request To Send) curto e CTS (Clear To Send) para "reservar" o canal.

PPP

• Enlace Point-To-Point (p2p).
• Mais utilizado em hosts domésticos.
• [RFC 1661], [RFC 2153].
• Camada de enlace, conectando dois nós.
  • Exemplo:
    • Linha telefônica discada serial (Modem 56K).
    • Sonet / SDH.
    • X.25
    • ISDN
• Preferida pelos usuários e seus ISPs.
• Deve prover:
  • Enquadramento do pacote.

  • Transparência -> não proibir padrões de bits.

  • Múltiplos protocolos da camada de rede.
  • Múltiplos tipos de enlace.
  • Detecção de erros.
  • Vida de conexão.

  • Simplicidade -> mais de 50 RFCs!!

  ==== Enquadramento ====
  • RFC 1662

    • 1	1	1	1 ou 2	variável	2 ou 4	1
      Flag	Endereço	Controle	Protocolo	Informação	Verificação	Flag
      01111110	11111111	00000011			CRC 16 bits	01111110

    Protocolo

    • IP é 21h (hexadecimal) -> RFC 1700.

    • Apple Talk 29h.
    • Realiza byte stuffing para evitar a detecção do flag na mensagem.

    • O byte de escape é 01111101.

    • O receptor remove os bytes de escape.
    • Se o próprio padrão do byte de controle for adicionado pela camada de aplicação, o número deve ser precedido pelo byte de controle.

Network Layer (Camada de Rede) -> Roteamento -> Datagrama -> Pacote

• Transferência de pacotes da origem para o destino.
• Roteamento Intermediário.
• Lida com transmissão "fim a fim".
• Deve conhecer a topologia da rede e subredes (roteadores) e escolher caminhos.
• Manter o balancemento de carga.
• Tratar as diferenças entre redes distintas. ==== Objetivos / Questões de Projeto ====
  • Serviços oferecidos a camada de transporte.
    • Objetivos:
      • Serviços independentes da tecnologia de sub-rede.
      • Isolar a camada de transporte da quantidade, tipo e topologia da sub-rede.
      • Uniformizar os endereços de rede oferecidos á camada de transporte. Por exemplo, endereços IPv4 e IPv6.
    • Qual serviço?
      • Orientado a conexão:
        • Companhias telefônicas.
        • Processo transmissor solicita conexão com processo receptor e negociam parâmetros de QoS.

        • A conexão identificada é mantida até o encerramento explicito do canal.

        • Comunicação em ambas as direções, pacotes entregues na seqüência.
        • Controle de fluxo, evitando overflow.
      • Não orientado a conexão:
        • Comunidade Internet.
        • Controle de erros/fluxos é atribuição dos hosts.
        • Primitivas SEND PACKET e RECEIVE PACKET.
        • Não há seqüência ou mesmo garantia de entrega.
        • Velocidade é mais importante que precisão.
  ==== Organização Interna da Camada de Rede ====

  • Conexão -> Circuito Virtual (CV).

  • Sem-Conexão -> Datagramas.

  • No CV estabelece-se uma rota durante todo o processo de comunicação.
  • No datagrama não há rota fixa (Internet).
  ==== Algoritmos de Roteamento ====
  • A camada de rede roteia pacotes.

  • Cada pacote pode necessitar vários hops para atingir o destino.

  • Os algoritmos são fundamentais -> parte do software da camada de rede responsável pelo roteamento -> decidir qual linha de saída utilizada na transmissão de um pacote de entrada (comutação).

  • Datagrama X "Session Routing" (CV).
  • Um algoritmo de roteamento deve apresentar:
    • Correção.
    • Simplicidade.

    • Robustez -> mudanças de topologia/tráfego.

    • Estabilidade.
    • Eqüidade.
    • Otimização.
    • Minimizar o retardo médio do pacote.
    • Maximizar o throughput total da rede.
    • Reduzir o número de hops de um pacote.
  ==== Algoritmos ====
  • Estáticos:
    • Cálculo off-line.
  • Adaptativos. ===== Princípios da Otimização =====
    • Se o roteador J estiver no caminho ótimo entre o roteador I e o roteador K, então o caminho ótimo de J para K também está.

      • O conjunto de rotas ótimas para o destino forma a sink tree (árvore de escoamento).

      O objetivo dos algoritmos é descobrir a sink tree e utilizá-la nos roteadores.

      • Árvores não possuem loops (como os grafos), logo um pacote é entregue num número finito de passos (hops).
    ===== Flooding (Inundação) =====
    • Todo pacote de entrada é enviado para toda linha de saída, exceto aquela em que chegou.

    • Normalmente, o cabeçalho do pacote tem um contador de hops, sendo decrementado em cada hop e descartado quando zerado.

    • Estático.
    • O contador é inicializado com o comprimento da origem ao destino, ou o diâmetro total da sub-rede.

    • O roteador de origem pode acrescentar um número de seqüência ao pacote recebido de seus hosts.

    • São necessários listas por roteador de origem, informandos quais pacotes com origem nesse ponto foram "vistos". Pacotes na lista não são inundados.
    • Pode ser feita "selective flooding" enviando o pacote para a linha que provavelmente esteja correta.
    ===== Distance Vector (Bellman - Ford) =====
    • Algoritmo dinâmico.
    • Cada roteador armazena uma tabela de distâncias (vetor).

    • Tais tabelas são atualizadas pela troca de informação com os vizinhos.

    • Implementado pela ARPANET original e ainda presente nos RIP.

    • Roteadores (routers) da Cisco e da Apple utilizam versões proprietárias otimizadas.

    • Entrada

      • Linha de saída preferencial a ser utilizada para esse destino.
      • Estimativas de tempo ou distância até o destino.
    • A métrica pode ser hops, retartdo médio em ms, número total de pacotes enfileirados na rota, etc.
      • Se for hop a distância é 1.

      • Comprimento da fila -> contar a fila.

      • Retardo -> medir com pacotes de ECHO.

        • ECHO -> Pacote sem informacão alguma. Vai "bate" e volta para quem enviou assim servindo para medir o tempo.

      • Se for unidade métrica retardo -> o roteador conhece o retardo médio até seus vizinhos.

        • A cada T ms cada roteador envia a seus vizinhos uma lista de seus retardos estimados para cada destino.

        • Também recebe uma lista idêntica de seus vizinhos.

        • Suponha uma lista vinda do roteador X, com Xi a estimativa de retardo até o roteador i (partindo de X).

        • Se o roteador conhecer o retardo m até X, então para atingir o roteador i temos Xi + m ms, através de X. Assim pode-se avaliar cada vizinho e escolher a melhor para a tabela.

      ===== Problemas com o Distance Vector =====

      1. Bouncing Effect

         • Formacão de "loops" (lacos) durante a faze de convergência do algoritmo.

         • Mensagens (pacotes) ficam "saltando" de um roteador para outro, sem chegar ao destino, sendo eliminadas pelo TTl (Time To Live).
         • Considerando que:
           1. A linha (link) 5 tem custo 10 e não 1.
           2. O link 2 (B-C) cai.
           3. O roteador B percebe e coloca métrica de inatingível (infinito).
           4. Antes de B anunciar a rota A o faz.

           5. Estabelece-se um loop de roteamento até que a métrica torna-se maior que 11.

      2. Count To Infinity
         • Impossibilidade do algoritmo convergir em algumas situacões de queda de enlace.
         • A rota nunca é marcada como inatingível e os pacotes ficam novamente "saltando"de um roteador para outro.
         • "Boas notícias se propagam depressa e más notícias demoram a chegar".

         • Exemplo:

           • Considere uma subrede Linear, sendo o retorno calculado pelo número de hops. Inicialmente A está desativado e todos os roteadores conscientes.

             • Quando A é ativado todos os roteadores toman ciência dele pela troca de vetores.
               • Na primeira troca B, toma conhecimento que seu vizinho da esquerda tem retardo zero até A e cria uma entrada em sua tableaa de roteamento.
               • Taxa de propagacão: 1hop/troca.
               • Logo Nhops, N trocas.
             • Contudo, considerando todos ativados.
               • O que ocorre quando o link A-B é desconectado?
               • O que C irá informar para B?
                 • Estará informando a B que ele consegue chegar a A.
               • Os roteadores tenderão ao infinito (limite), mas qual seu valor numérico?
                 • Caminho mais longo mais 1.
               • E se a métrica for retardo de tempo?
                 • Não tem como saber por causa que este valor varia bastante.
    ===== Solucões =====

    1. Hop-Count Limit

       • O infinito é representado por um número.
       • Tal número não deve ser muito grande para que o algorítmo não leve muito para convergir.
       • Porém a distância máxima na rede não deve ficar muito limitada.

    2. Split Horizon

       • Informacões de roteamento não devem ser enviadas de volta ao roteador que as originou.
       • Soluciona lacos entre dois roteadores, mas, e entre mais de dois roteadores?
       • No estado inicial (To) na fig. b o roteador C diz a verdade para D sobre a distância até A, mas informa infinito para B.
       • O que ocorre, AGORA, quando A cai?
       • Qual a taxa de propagacão das más notícias?
         • A --- B
           • \ /
             • C | D
       • O que ocorre quando CD cai?
       • A e B informam infinito para C como métrica até D.
       • C informa infinito para A e B.
       • O que B informa para A?
       • E com B o que ocorre?

    3. Hold Down

       • Quando uma rota torna-se inatingível, deve ser restabelecida apenas após algum tempo.
       • Período maior que o tempo de propagacão da mensagem em toda a rede.

    4. Triggered Updates (Atualizacões Engatilhadas)

       • Evitar o poling.
       • Utilizar trigger.
  ===== Roteamento Hierárquico =====
  • Há agrupamento de roteadores por regiões ou em sistemas autônomos(SA).
  • Todos os roteadores dentro da região ou SA rodam o mesmo algoritmo de roteamento e possui informações sobre cada um dos outros.
  • Conexão entre as regiões ou AS`s é feito por um roteador específico.

  • Modelo Homogêneo -> visão "plana" dos roteadores.

  • Problema de Escala -> um DV na Internet pública jamais convergiria.

  • Agrupar os roteadores em regiões -> Autonomous Systems (AS).

  • Todos os roteadores de um AS rodam o mesmo algoritmo.

  • Dentro da AS o algoritmo é o protocolo de roteamento intra-AS.

  • Roteadores devem rotear para sistemas externos do AS -> roteadores de borda (gateways routers).