Especificação do Trabalho

Descrição e Objetivo

Este trabalho consistirá na implementação de um simulador de redes IPv4 bastante simplificado. A ideia é desenvolver um programa que simule, de maneira superficial, o comportamento de um roteador ou host incluindo tarefas como a geração de um datagrama, gerenciamento de tabela de roteamento e encaminhamento. Para simular uma rede com múltiplos roteadores ou hosts, várias instâncias do programa deverão ser executadas. As instâncias se comunicarão através de sockets TCP, simulando, assim, a(s) interface(s) de rede do dispositivo.

Considere, por exemplo, a topologia abaixo:

Esta topologia é formada por quatro dispositivos: um roteador, com três interfaces de rede, conectado a três hosts, cada um com uma única interface. As retas representam enlaces interconectando os dispositivos e os endereços mostrados correspondem aos IPs de cada interface de rede.

Esta topologia poderia ser construída no simulador a ser desenvolvido neste trabalho através da seguinte organização:

Neste exemplo hipotético, são usados três computadores diferentes (retângulos com linhas contínuas), executando um total de 4 instâncias do simulador (retângulos com linhas tracejadas). Note que o computador mais à esquerda executa duas instâncias do simulador (de fato, todas as instâncias poderiam ser executadas em um único host físico). Cada uma das instâncias abre um socket TCP e aguarda conexões em uma porta específica. As instâncias executadas no host físico A representam os hosts 1 e 3 da topologia simulada (o host 1 é simulado pela instância que roda na porta 5000, enquanto o host 3 pela instância que roda na porta 5001). O host 2 da topologia simulada é representado pela instância que roda no host físico B. Finalmente, o roteador da topologia simulada é representado pela instância do simulador executada no host físico C.

Cada host físico tem seu endereço IP (e.g., 192.168.0.50 para o host C) e estes endereços servem para que conexões TCP sejam abertas entre as instâncias dos simuladores. Para cada interface de rede do dispositivo simulado correspondente, a instância do simulador abrirá uma conexão TCP para a instância que representa o dispositivo simulado conectado na outra ponta do enlace. Para simular a transmissão de um pacote entre dois dispositivos, a instância do simulador responsável pelo transmissor deve enviar o pacote pelo socket correspondente à interface desejada.

Além do desenvolvimento do código, os grupos deverão utilizar seus simuladores para resolver um pequeno problema de roteamento. Cada grupo receberá a descrição de uma pequena topologia de rede, associada a um conjunto de requisitos de roteamento (e.g., permitir a comunicação bidirecional entre os hosts X e Y através do caminho A - B - C - D). O grupo deverá, então, gerar tabelas de roteamento para cada dispositivo da topologia de forma a atender aos requisitos solicitados.

Tanto a implementação do simulador, quanto a solução do problema de roteamento deverão ser documentadas na forma de um pequeno relatório. Finalmente, o conteúdo do relatório deverá ser apresentado oralmente pelo grupo em data a ser determinada posteriormente.

Em resumo, o trabalho consiste das seguintes tarefas:

1. Implementação do programa simulador.
2. Resolução do problema de roteamento.
3. Escrita do relatório.
4. Apresentação oral.

As seções a seguir detalham cada um destes pontos.

Implementação do Programa Simulador

Para simplificar a compreensão e desenvolvimento do simulador, esta especificação dividirá este projeto em algumas etapas (ou versões), a saber:

1. Versão que permite apenas a comunicação em um único salto, com pacote em formato livre.
2. Versão que permite apenas a comunicação em um único salto, com pacote no formato do datagrama IPv4 e IPs virtuais.
3. Versão que permite comunicação em múltiplos saltos, com dispositivos intermediários realizando encaminhamento com base em tabelas de roteamento fornecidas pelo usuário.

Note que apenas a última versão (i.e., a completa) deverá ser entregue. Esta divisão é puramente didática, com o propósito de facilitar a compreensão. Note ainda que as primeiras versões exigem menos conhecimento acerca da ementa da disciplina que as demais. Esta divisão, portanto, tem o objetivo secundário de ilustrar como o projeto pode ser desenvolvido aos poucos ao longo do período letivo.

Versão com comunicação de um salto e pacote em formato livre

O programa desenvolvido nesta versão deverá receber como argumentos:

1. Um número de porta na qual o processo aguardará por dados dos demais processos (i.e., que simulam outros dispositivos na rede).
2. Um arquivo que especifique a lista de vizinhos diretos do dispositivo simulado na rede.

O arquivo de que trata o item 2 deverá conter um vizinho por linha. Para cada vizinho, deverão ser especificados o endereço IP e a porta que identificam o processo que o simula. IP e porta deverão ser separados por um espaço em branco. Um exemplo de arquivo de entrada pode ser visto a seguir:

Neste exemplo, são especificados os endereços de 3 processos que atuarão como vizinhos do processo a ser disparado. Os dois primeiros vizinhos estão em execução no host de IP 192.168.0.10, um na porta 5000 e o outro na porta 5001. Já o terceiro vizinho é simulado por um processo que reside no host cujo endereço IP é 192.168.0.5 e escuta na porta TCP 5000.

Ao iniciar sua execução, o programa abrirá um socket TCP para escuta na porta informada na linha de comando. O programa também lerá o arquivo de vizinhos e armazenará em memória a lista dos processos com os quais deverá estabelecer comunicação. O programa, no entanto, não deve imediatamente tentar abrir conexão para os vizinhos especificados no arquivo. Ao contrário, ele deverá fornecer uma interface através da qual o usuário possa solicitar que as conexões sejam abertas. Apenas no momento da solicitação do usuário, o programa deverá tentar estabelecer as conexões TCP para seus vizinhos. A forma de interface com o usuário não é importante. Sugere-se uma simples interface baseada em linha de comando, mas o grupo é livre para utilizar outras formas de interação com o usuário, se assim preferir.

Qualquer que seja a forma de interface com o usuário, esta deverá permitir também que o usuário solicite a geração e transmissão de uma mensagem. Ao utilizar esta opção, o usuário deverá fornecer uma string de comprimento arbitrário e o endereço IP e porta de um dos vizinhos para quem a mensagem deve ser enviada. De posse destas informações, o programa deverá gerar um pacote contendo a string especificada e deverá enviá-lo pelo socket aberto para o vizinho em questão. Não é necessário implementar qualquer mecanismo de ack ou retransmissão.

Ao receber um pacote, o processo que simula o destinatário deve gerar algum tipo de aviso ao usuário (e.g., imprimir uma mensagem no terminal, ou gerar um diálogo de confirmação). Este aviso deverá exibir a string recebida. Nenhuma outra ação por parte do receptor é requerida.

Note que:

1. Se um processo A é vizinho de um outro processo B, A possuirá dois sockets de comunicação abertos com B: um da conexão que A iniciou com B e outro da conexão que B iniciou com A. Sempre que for transmitir um pacote para um vizinho, um processo deverá utilizar o socket relativo à conexão que ele próprio iniciou.
2. Qualquer que seja a forma de interface com o usuário, o programa deve sempre estar preparado para responder a dois tipos de evento: um comando do usuário (e.g., abrir conexão com os vizinhos, enviar pacote) ou a recepção de um pacote enviado por um vizinho. Para isso, sugere-se a utilização de threads ou de funções convenientes da API de sockets como a select(), mas o grupo é livre para escolher qualquer outra solução que julgue conveniente e atenda a este requisito.

Versão com comunicação de um salto, pacotes em formato de datagrama IPv4 e IPs virtuais

Nesta segunda versão, há duas mudanças em relação à versão anterior. Em primeiro lugar, o programa deve receber um terceiro argumento ao ser executado. Este argumento é uma string indicando o caminho para um arquivo que conterá a configuração de endereços IPs para as interfaces do dispositivo simulado. Em outras palavras, cada linha deste arquivo deverá especificar um endereço IP a ser usado na simulação como o endereço da interface virtual relacionada a cada vizinho especificado no arquivo de vizinhos. Por exemplo:

Este arquivo especifica os endereços para 3 interfaces simuladas (i.e., sockets para outros processos do simulador). Os endereços devem ser atribuídos às interfaces simuladas na mesma ordem que os vizinhos são especificados no arquivo da lista de vizinhos. Por exemplo, considerando a lista de vizinhos hipotética apresentada na seção anterior, a interface simulada usada para comunicação com o vizinho representado pelo processo executado no endereço 192.168.0.10 na porta 5000 deve ter um endereço IP virtual 10.0.0.1 com máscara de sub-rede 255.255.255.0.

Consequentemente, o número de linhas do arquivo de endereços das interfaces deve corresponder ao número de linhas do arquivo com a lista de vizinhos. Caso contrário, o programa deve acusar o erro e abortar a execução.

A segunda mudança desta versão em relação à versão anterior diz respeito ao formato das mensagens transmitidas entre os processos. Sempre que o usuário requisitar a transmissão de uma mensagem, a string especificada deverá ser empacotada em um cabeçalho IPv4. O grupo deverá consultar o material didático da disciplina (e.g., slides das aulas, livro texto) para obter os campos, números de bits e convenções pertinentes.

Algumas observações sobre o preenchimento dos campos do cabeçalho IPv4 nesta versão da implementação:

1. Os campos type-of-service, flags, fragment offset, upper layer, checksum deverão ser zerados (eles não serão utilizados neste projeto).
2. Este projeto também não usará o campo de opções do cabeçalho IPv4.
3. O campo TTL deve ser sempre inicializado com o valor 7.
4. O campo de endereço de origem deverá ser preenchido com o endereço virtual da interface simulada (i.e., socket) usado para a transmissão do pacote.
5. O campo de endereço de destino não é importante nesta versão (mas será importante na terceira, e última, versão, descrita na próxima seção).
6. Conforme estudado em sala de aula, o campo length limita o tamanho máximo de um datagrama IP em 65535 bytes (contando os cabeçalhos). Caso a string especificada pelo usuário seja grande demais, esta deve ser quebrada e transmitida em múltiplos datagramas individualmente. Note que, neste caso, estamos falando de datagramas separados (e não de fragmentos de um mesmo datagrama).

Com a mudança no formato de mensagem gerada pelo transmissor, o código do receptor também deve ser alterado para interpretar corretamente as mensagens recebidas.

Versão com encaminhamento

A terceira, e última, versão da implementação adiciona a funcionalidade de encaminhamento de pacotes ao simulador, permitindo assim comunicação através de múltiplos saltos. Para isso, será necessário um pequeno número de alterações em relação à versão anterior.

A primeira alteração necessária é relacionada aos parâmetros de entrada para a execução do programa. Além dos três parâmetros da versão anterior (número de porta, arquivo com a lista de vizinhos, arquivo com a lista de endereços das interfaces), esta versão contará com um quarto parâmetro: um arquivo contendo as entradas de uma tabela de roteamento.

Cada linha do arquivo corresponderá a uma entrada da tabela de roteamento do dispositivo simulado. Em cada entrada, deverão ser especificados um endereço da sub-rede de destino (endereço e máscara de sub-rede) e índice da interface virtual de saída (começando do 0, e contado na mesma ordem do arquivo com a lista de endereços das interfaces). Um exemplo hipotético deste arquivo pode ser visto a seguir:

Note que não há necessariamente uma correspondência entre o número de linhas neste arquivo e o número de linhas dos demais arquivos de entrada. Note ainda que este arquivo pode ser, inclusive, vazio (denotando uma tabela de roteamento sem entradas).

Ao iniciar sua execução, o programa deve ler o arquivo da tabela de roteamento e armazenar o conteúdo da tabela em memória. A leitura deste arquivo deve ser realizada após a leitura dos dois outros arquivos de entrada, permitindo assim que o programa realize algumas verificações de consistência. Em particular, para cada entrada da tabela, o programa deve verificar se:

• a interface de saída realmente existe (e.g., o dispositivo simulado só possui três interfaces, mas uma das entradas lista a interface de índice 10); e
• se a máscara de sub-rede faz sentido (e.g., 255.255.255.229 é uma máscara inválida).

Caso alguma inconsistência seja detectada, o programa deve exibir uma mensagem explicando o erro e abortar a execução.

Além de armazenar as entradas da tabela de roteamento especificadas no arquivo de entrada, para cada interface virtual do dispositivo simulado o programa deve automaticamente adicionar uma entrada do tipo:

<endereço da sub-rede da interface> <máscara da sub-rede> <índice da interface>

O endereço da sub-rede deve ser calculado pelo programa com base no endereço IP e máscara de sub-rede de cada interface virtual.

A segunda alteração desta versão em relação à versão anterior diz respeito ao endereço de destino na geração/envio de uma mensagem. Quando o usuário requisitar o envio de uma mensagem, o endereço de destino informado deverá corresponder ao endereço virtual de uma das interfaces simuladas do destinatário, ao invés do endereço IP e porta do processo que simula o destinatário (como feito até a versão anterior). Este endereço virtual especificado pelo usuário deverá ser utilizado como endereço de destino no datagrama IP gerado pelo simulador.

Além disso, para que o nó de origem de uma mensagem decida por qual interface simulada (i.e., socket) irá enviar o datagrama recém-criado, ele consultará a tabela de roteamento do dispositivo simulado, usando o endereço de destino do datagrama. Caso não haja uma entrada adequada na tabela, o programa deverá exibir uma mensagem de erro explicando que o pacote não pode ser enviado, mas a execução não deverá ser abortada.

Note que, nesta versão, um pacote pode ser enviado a um dispositivo simulado que não é o destinatário final. Com isso, uma terceira alteração nesta versão em relação às versões anteriores diz respeito ao processamento dos pacotes recebidos. Ao receber um pacote, o nó deverá realizar as seguintes ações (nesta ordem):

1. Verificar o endereço IP de destino informado no datagrama. Se o endereço de destino for igual ao endereço virtual de uma das interfaces do dispositivo simulado:
   1. O programa deve alertar o usuário e exibir o conteúdo da mensagem recebida. Nenhuma outra ação é necessária neste caso.
2. Caso contrário:
   1. O programa deve decrementar o TTL do datagrama. Caso o novo valor de TTL seja zero, o programa deve gerar uma mensagem de aviso ao usuário (e.g., imprimir na tela) e descartar o pacote, mas não deve abortar a execução. Nenhuma outra ação é necessária neste caso.
   2. O programa deve consultar sua tabela de roteamento, buscando a rota adequada àquele IP de destino. Caso não haja uma entrada adequada na tabela, o programa deverá exibir uma mensagem de erro explicando que o pacote não pode ser enviado, mas a execução não deverá ser abortada. Nenhuma outra ação é necessária neste caso.
   3. O programa deve usar a rota encontrada para selecionar a interface simulada (i.e., socket) pelo qual o pacote será enviado.

Tanto no nó de origem quanto nos nós intermediários, as buscas na tabela de roteamento deverão ser realizadas conforme as convenções do protocolo IP (e.g., busca pelo prefixo mais longo).

Resolução de problema de roteamento

Cada grupo deverá requisitar (com antecedência) por e-mail ao professor uma instância de um problema de roteamento. O professor fornecerá instâncias diferentes para cada grupo, embora todas terão níveis de complexidade similares. As instâncias serão especificadas na forma de uma figura ilustrando os dispositivos da rede (hosts e roteadores), bem como enlaces interconectando-os. Além disso, a instância conterá um conjunto de requisitos de comunicação (descritos textualmente) que deverão ser atendidos pela solução.

De posse do simulador desenvolvido e da sua instância, cada grupo deverá propor uma solução. Esta solução consiste simplesmente na tabela de roteamento de cada dispositivo da topologia, com entradas que atendam aos requisitos especificados. No relatório deste projeto, deverão constar tanto a instância do grupo quanto a solução encontrada. Esta solução deverá ser mostrada também na apresentação oral do trabalho.

Relatório

Além da parte de implementação e da resolução da instância do problema de roteamento atribuída ao grupo, este trabalho inclui um relatório. O objetivo do relatório é documentar a implementação realizada e a solução do problema atribuído ao grupo. Em particular, espera-se que o conteúdo do relatório contemple os seguintes aspectos:

• informações básicas sobre a implementação (e.g., qual a linguagem de programação utilizada, bibliotecas externas necessárias, como compilar o simulador);
• explicação sobre a arquitetura do software desenvolvido (e.g., quais são os módulos que o compõe, como estes módulos se comunicam);
• apresentação da instância de roteamento atribuída ao grupo (e.g., figura da topologia, requisitos de comunicação); e
• solução dada à instância do problema de roteamento (e.g., tabela de rota de cada dispositivo).

Requisitos e Restrições

A parte de implementação do trabalho pode ser feita em qualquer uma das seguintes linguagens: C, C++, C#, Java, Python, Pascal. Devem ser observadas as seguintes restrições adicionais:

• todas as funcionalidades citadas nesta especificação devem ser implementadas por código desenvolvido pelos próprios membros do grupo (i.e., não serão aceitos códigos copiados total ou parcialmente de terceiros e funcionalidades como o armazenamento e consulta da tabela de roteamento devem ser originais do grupo); e
• o código final deve ser compilável/executável sem a necessidade de bibliotecas, frameworks ou ferramentas pagas.

De maneira análoga, o relatório é de formato livre, sem limites inferiores ou superiores de páginas. Apenas como um guia geral, 3 páginas devem ser suficientes (embora não necessárias) para contemplar todos os itens listados na seção anterior.

Os grupos poderão ser formados com no mínimo 2 e no máximo 5 alunos.

Apresentação

Como parte da avaliação, o grupo deverá realizar uma apresentação curta do trabalho desenvolvido para o restante da turma durante o horário da aula em data a ser combinada com o professor posteriormente. A apresentação deverá ser realizada por todos os integrantes e contemplar os seguintes itens:

• visão geral do funcionamento do código;
• exemplo de execução do código;
• instância do problema de roteamento atribuída ao grupo; e
• solução dada pelo grupo à instância.

O tempo máximo de apresentação será de 15 minutos. A apresentação poderá ser baseada em slides ou não, de acordo com decisão de cada grupo.

Critério de Avaliação

Cada trabalho receberá uma nota variando de 0 a 10. Esta pontuação será dividida nas seguintes proporções:

1. Até 5,0 pontos para a implementação do simulador, dos quais:
   1. Até 0,5 pontos para a leitura dos parâmetros da linha de comando.
   2. Até 1,0 ponto para a manipulação dos sockets no código do simulador.
   3. Até 1,0 ponto para a criação, manipulação e interpretação dos datagramas no formato correto do IPv4.
   4. Até 1,0 ponto para a criação, manipulação e consulta às tabelas de roteamento.
   5. Até 0,5 pontos para o encaminhamento de datagramas segundo as convenções do IPv4.
   6. Até 0,5 pontos para a existência e qualidade de comentários no código fonte.
   7. Até 0,5 pontos para outros aspectos relevantes de implementação.
2. Até 3,0 pontos para o relatório, dos quais:
   1. Até 0,5 pontos para as informações básicas sobre a implementação.
   2. Até 0,5 pontos para a visão geral do código.
   3. Até 2,0 pontos para a solução da instância do problema de roteamento atribuído ao grupo.
3. Até 2,0 pontos para a apresentação, dos quais:
   1. Até 1,5 ponto para a qualidade de apresentação do conteúdo do relatório.
   2. Até 0,5 ponto para a correta execução da implementação.

As implementações serão avaliadas apenas em relação à correção do código e aderência a esta especificação. Não haverá pontuação associada ao desempenho/eficiência da implementação.

Entrega

A data limite para a entrega do trabalho está disponível no calendário da página da disciplina. A entrega deverá ser realizada por e-mail, através do endereço dpassos@ic.uff.br. O e-mail deverá conter:

• Identificador do trabalho (e.g., “Trabalho de Redes I”).
• Lista dos integrantes do grupo.
• Código fonte da implementação.
• Instruções de compilação/execução/uso da implementação (possivelmente no relatório).
• Relatório.

Serão aceitos, sem penalidade, e-mails enviados até as 19:59 da data limite (i.e., até o horário da aula). Os e-mails de entrega de trabalho terão seus recebimentos devidamente confirmados. É responsabilidade do grupo garantir que o trabalho seja recebido, aguardando pela confirmação e reenviando a mensagem caso não a recebam em tempo razoável. Em caso de dúvidas ou correções relacionadas a esta especificação, também é responsabilidade de cada grupo entrar em contato (seja pessoalmente, ou através do mesmo endereço de e-mail) requisitando esclarecimentos dentro do prazo de entrega do trabalho.

Uma vez entregue o trabalho, não serão aceitas alterações (nem inclusões, nem remoções) na lista de integrantes do grupo em nenhuma hipótese. Por isso, sugere-se atenção no momento do envio da mensagem para que a lista contenha todos os integrantes do grupo.