ANDRÉ SALSA
CÉSAR KALLAS
FERNANDO HAFNER

REDES DE COMPUTADORES iI
Relatório da Tarefa de Programação II

Pontifícia Universidade Católica de Campinas
Faculdade de Engenharia da Computação
Março /2006

André Salsa					email: salsandre@gmail.com
Fernando Hafner	R.A. 01002609	email: fernando.hafner@gmail.com
César Kallas		R.A. 02099224	email: cesarkallas@gmx.net

Divisão das Notas : 

Fernando Hafner	-	35%
André Salsa		-	35%
César Kallas	-	30%

DiSTANCE VECTOR

Trabalho requisitado pelo professor de Redes de Computadores II, ministrada pelo professor Juan, da Pontifícia Universidade Católica, com o intuito de avaliação acadêmica dos alunos, para efeito de cálculo da média final.

Pontifícia Universidade Católica de Campinas
Faculdade de Engenharia da Computação
Março /2006

1 ) Nível de Atendimento aos Requisitos da Atividade

Para a atividade de Distance Vector, foi requisitado aos aluno da disciplina Redes de Computadores II, que fossem desenvolvidas as atividades relacionadas com protocolo de roteamento ligados à vetores. Ambas as atividades foram desenvolvidas pelo grupo. 

2 ) Descrição das Rotinas Implementadas

	Segue abaixo a descrição do que foi implementado em cada uma das rotinas : 

2.1) Rotinas do Protocolo GBN

 rtinit0()  – a função  rtinit0()  tem como objetivo a inicialização do vetor de distância entre os nós. Nela é preenchido uma matriz 4x4 aonde é declarada a distância dele mesmo (nó 0) até os outros nós ligados diretamente (vizinhos).
Depois de preenchido a matriz, a função deve avisar os vizinhos seus que já sabe a menor distância dele até eles.  Essa função vai se repetir para os outros nós.

rtupdate0 -  a função rtupdate0 recebe um novo pacote com caminhos possivelmente mais curtos entre os nós. Com esse pacote, a função vai analisar se o dado oferecio realmente é válido (se o caminho é menor que já existente) e atualiza a sua tabela de menor caminho. Essa função vai se repetir para os outros nós.

3 ) Instruções para Geração e Execução do Programa
	Para geração do programa utilizando o ambiente Linux e o compilador GCC, basta compilar o arquivo fonte normalmente sem nenhum parâmetro adicional. O mesmo vale para a execução do programa.
Exemplo:
[chk@cesarkallas distance-vetor]$ make
cc    -c -o prog3.o prog3.c
cc    -c -o node0.o node0.c
node0.c:8: warning: useless keyword or type name in empty declaration
cc    -c -o node1.o node1.c
node1.c:9: warning: useless keyword or type name in empty declaration
cc    -c -o node2.o node2.c
node2.c:8: warning: useless keyword or type name in empty declaration
cc    -c -o node3.o node3.c
node3.c:8: warning: useless keyword or type name in empty declaration
gcc -g -o distance_vector prog3.o  node0.o  node1.o  node2.o  node3.o
[chk@cesarkallas distance-vetor]$     

[chk@cesarkallas distance-vetor]$ ./distance_vector
Enter TRACE:3

Tabela de distancias inicial do nó 0:
                via
   D0 |    1     2    3
  ----|-----------------
     1|    1     7    15
dest 2|    5     3    17
     3|    9    13     7
    TOLAYER2: source: 0, dest: 1
              costs:0  1  3  7
    TOLAYER2: scheduling arrival on other side
    TOLAYER2: source: 0, dest: 2
              costs:0  1  3  7
    TOLAYER2: scheduling arrival on other side
    TOLAYER2: source: 0, dest: 3
              costs:0  1  3  7
    TOLAYER2: scheduling arrival on other side

Tabela de distancias inicial do nó 1:
             via
   D1 |    0     2
  ----|-----------
     0|    1     3
dest 2|    3     1
     3|  999   999
    TOLAYER2: source: 1, dest: 0
              costs:1  0  1  999
    TOLAYER2: scheduling arrival on other side
    TOLAYER2: source: 1, dest: 2
              costs:1  0  1  999
    TOLAYER2: scheduling arrival on other side

Tabela de distancias inicial do nó 2:
                via
   D2 |    0     1    3
  ----|-----------------
     0|    3     5     7
dest 1|    7     1     5
     3|    8     4     2
    TOLAYER2: source: 2, dest: 0
              costs:3  1  0  2
    TOLAYER2: scheduling arrival on other side
    TOLAYER2: source: 2, dest: 1
              costs:3  1  0  2
    TOLAYER2: scheduling arrival on other side
    TOLAYER2: source: 2, dest: 3
              costs:3  1  0  2
    TOLAYER2: scheduling arrival on other side

Tabela de distancias inicial do nó 3:
             via
   D3 |    0     2
  ----|-----------
     0|    7    11
dest 1|  999   999
     2|   16     2
    TOLAYER2: source: 3, dest: 0
              costs:7  999  2  0
    TOLAYER2: scheduling arrival on other side
    TOLAYER2: source: 3, dest: 2
              costs:7  999  2  0
    TOLAYER2: scheduling arrival on other side
MAIN: rcv event, t=0.947, at 3 src: 0, dest: 3, contents:   0   1   3   7

Tabela de distancias atualizada 3:
             via
   D3 |    0     2
  ----|-----------
     0|    7    11
dest 1|    8   999
     2|   16     2
    TOLAYER2: source: 3, dest: 0
              costs:7  8  2  0
    TOLAYER2: scheduling arrival on other side
    TOLAYER2: source: 3, dest: 2
              costs:7  8  2  0
    TOLAYER2: scheduling arrival on other side
MAIN: rcv event, t=0.992, at 0 src: 1, dest: 0, contents:   1   0   1 999

Tabela de distancias atualizada 0:
                via
   D0 |    1     2    3
  ----|-----------------
     1|    1     7    15
dest 2|    2     3    17
     3|    9    13     7
    TOLAYER2: source: 0, dest: 1
              costs:0  1  2  7
    TOLAYER2: scheduling arrival on other side
    TOLAYER2: source: 0, dest: 2
              costs:0  1  2  7
    TOLAYER2: scheduling arrival on other side
    TOLAYER2: source: 0, dest: 3
              costs:0  1  2  7
    TOLAYER2: scheduling arrival on other side
MAIN: rcv event, t=1.209, at 3 src: 2, dest: 3, contents:   3   1   0   2

Tabela de distancias atualizada 3:
             via
   D3 |    0     2
  ----|-----------
     0|    7     5
dest 1|    8     3
     2|   16     2
    TOLAYER2: source: 3, dest: 0
              costs:5  3  2  0
    TOLAYER2: scheduling arrival on other side
    TOLAYER2: source: 3, dest: 2
              costs:5  3  2  0
    TOLAYER2: scheduling arrival on other side
MAIN: rcv event, t=1.276, at 3 src: 0, dest: 3, contents:   0   1   2   7
MAIN: rcv event, t=1.642, at 2 src: 0, dest: 2, contents:   0   1   3   7
MAIN: rcv event, t=1.871, at 1 src: 0, dest: 1, contents:   0   1   3   7

Tabela de distancias atualizada 1:
             via
   D1 |    0     2
  ----|-----------
     0|    1     3
dest 2|    3     1
     3|    8   999
    TOLAYER2: source: 1, dest: 0
              costs:1  0  1  8
    TOLAYER2: scheduling arrival on other side
    TOLAYER2: source: 1, dest: 2
              costs:1  0  1  8
    TOLAYER2: scheduling arrival on other side
MAIN: rcv event, t=2.166, at 2 src: 1, dest: 2, contents:   1   0   1 999

Tabela de distancias atualizada 2:
                via
   D2 |    0     1    3
  ----|-----------------
     0|    3     2     7
dest 1|    7     1     5
     3|    8     4     2
    TOLAYER2: source: 2, dest: 0
              costs:2  1  0  2
    TOLAYER2: scheduling arrival on other side
    TOLAYER2: source: 2, dest: 1
              costs:2  1  0  2
    TOLAYER2: scheduling arrival on other side
    TOLAYER2: source: 2, dest: 3
              costs:2  1  0  2
    TOLAYER2: scheduling arrival on other side
MAIN: rcv event, t=2.407, at 0 src: 2, dest: 0, contents:   3   1   0   2

Tabela de distancias atualizada 0:
                via
   D0 |    1     2    3
  ----|-----------------
     1|    1     7    15
dest 2|    2     3    17
     3|    9     4     7
    TOLAYER2: source: 0, dest: 1
              costs:0  1  2  4
    TOLAYER2: scheduling arrival on other side
    TOLAYER2: source: 0, dest: 2
              costs:0  1  2  4
    TOLAYER2: scheduling arrival on other side
    TOLAYER2: source: 0, dest: 3
              costs:0  1  2  4
    TOLAYER2: scheduling arrival on other side
MAIN: rcv event, t=2.421, at 2 src: 3, dest: 2, contents:   7 999   2   0
MAIN: rcv event, t=2.811, at 1 src: 2, dest: 1, contents:   3   1   0   2

Tabela de distancias atualizada 1:
             via
   D1 |    0     2
  ----|-----------
     0|    1     3
dest 2|    3     1
     3|    8     3
    TOLAYER2: source: 1, dest: 0
              costs:1  0  1  3
    TOLAYER2: scheduling arrival on other side
    TOLAYER2: source: 1, dest: 2
              costs:1  0  1  3
    TOLAYER2: scheduling arrival on other side
MAIN: rcv event, t=3.293, at 2 src: 3, dest: 2, contents:   7   8   2   0
MAIN: rcv event, t=3.602, at 3 src: 2, dest: 3, contents:   2   1   0   2

Tabela de distancias atualizada 3:
             via
   D3 |    0     2
  ----|-----------
     0|    7     4
dest 1|    8     3
     2|   16     2
    TOLAYER2: source: 3, dest: 0
              costs:4  3  2  0
    TOLAYER2: scheduling arrival on other side
    TOLAYER2: source: 3, dest: 2
              costs:4  3  2  0
    TOLAYER2: scheduling arrival on other side
MAIN: rcv event, t=4.063, at 2 src: 0, dest: 2, contents:   0   1   2   7
MAIN: rcv event, t=4.104, at 0 src: 3, dest: 0, contents:   7 999   2   0
MAIN: rcv event, t=4.169, at 2 src: 3, dest: 2, contents:   5   3   2   0
MAIN: rcv event, t=4.330, at 0 src: 3, dest: 0, contents:   7   8   2   0
MAIN: rcv event, t=4.643, at 1 src: 0, dest: 1, contents:   0   1   2   7
MAIN: rcv event, t=5.213, at 0 src: 3, dest: 0, contents:   5   3   2   0
MAIN: rcv event, t=5.384, at 3 src: 0, dest: 3, contents:   0   1   2   4
MAIN: rcv event, t=5.820, at 1 src: 2, dest: 1, contents:   2   1   0   2
MAIN: rcv event, t=6.042, at 2 src: 1, dest: 2, contents:   1   0   1   8
MAIN: rcv event, t=6.071, at 0 src: 1, dest: 0, contents:   1   0   1   8
MAIN: rcv event, t=6.532, at 1 src: 0, dest: 1, contents:   0   1   2   4
MAIN: rcv event, t=7.021, at 0 src: 2, dest: 0, contents:   2   1   0   2
MAIN: rcv event, t=7.160, at 2 src: 0, dest: 2, contents:   0   1   2   4
MAIN: rcv event, t=7.405, at 0 src: 1, dest: 0, contents:   1   0   1   3
MAIN: rcv event, t=8.086, at 0 src: 3, dest: 0, contents:   4   3   2   0
MAIN: rcv event, t=8.639, at 2 src: 1, dest: 2, contents:   1   0   1   3
MAIN: rcv event, t=8.943, at 2 src: 3, dest: 2, contents:   4   3   2   0

Simulator terminated at t=8.942584, no packets in medium

4 ) Opiniões sobre a Atividade
	A atividade permitiu relembrar conceitos apresentados na disciplina Redes de Computadores I, como os modos de roteamento existentes e como a agilidade dos algoritmos podem diminuir o tempo gasto para alcançar um objetivo (nó). 

4.1 ) Tempo Gasto
	O tempo total gasto para o desenvolvimento da atividade ( leitura/estudo da documentação e implementação) foi de 8 dias; dedicando aproximadamente 1.5 horas por dia.

4.2 ) Considerações Positivas
	O programa que nos foi apresentado como base nos permitiu observar como funciona o o algoritimo de roteamente por vetores de distância na prática. A flexibilidade do programa base, ajudou consideravelmente na execução de testes, podendo demonstrar como a distância de um nó à outro pode ser menor, mesmo passado por mais caminhos.

4.3 ) Considerações Negativas
	Não há uma animação gráfica demonstrando o caminho percorrido por um pacote, ajudaria muito a entender melhor em uma grande matriz.

4.4 ) Sugestões para Melhoria da Atividade
	Ferramente gráfica de simulação de roteamento de pacotes pelos nós.

Anexo 1 – Fonte dos programas

node0.c

#include <stdio.h>
extern struct rtpkt {
  int sourceid;       /* id of sending router sending this pkt */
  int destid;         /* id of router to which pkt being sent 
                         (must be an immediate neighbor) */
  int mincost[4];    /* min cost to node 0 ... 3 */
  };

extern int TRACE;
extern int YES;
extern int NO;

struct distance_table 
{   int costs[4][4];
} dt0;

int connectcosts0[4] = { 0,  1,  3, 7 };
// caminhos minimos
int mincost0[4]; 

int noway0=4;
int myself0 = 0;
	
/* students to write the following two routines, and maybe some others */

void rtinit0() 
{
	int i,j;
	struct rtpkt packet;
	for (i=0; i<4; i++)
		for (j=0; j<4; j++)
		{
			if (j== noway0 || i == noway0)
				dt0.costs[i][j] = connectcosts0[noway0];		// não sei o caminho
			else
			{
				if (j == myself0)
					dt0.costs[i][j]= connectcosts0[i];	// link direto
				else if (i == myself0)
					dt0.costs[i][j]= 2 * connectcosts0[j];	// não sera usado
				else if (i == j)
					dt0.costs[i][j] = connectcosts0[i];	// link direto
				else 
					dt0.costs[i][j] = connectcosts0[j]* 2 + connectcosts0[i]; // vou para j, volto para 1, e vou para i (i atraves de j)
			}
		}

	if (TRACE>1)
	{	printf("\nTabela de distancias inicial do nó %d:\n", myself0);			
		printdt0(&dt0);
	}

	// acha os caminhos minimos
	for(j=0;j<4;j++)
		mincost0[j] = dt0.costs[j][j];

	// envia os caminhos minimos para os vizinhos;
	for (i=0; i<4; i++)
		if (i!= myself0 && i!= noway0)
		{
			packet.destid = i;
			packet.sourceid= myself0;
			for(j=0;j<4;j++) 
				packet.mincost[j] = mincost0[j];
			tolayer2(packet);
		}
}

  
void rtupdate0(rcvdpkt)
  struct rtpkt *rcvdpkt;
{
	int change = 0;
	int i, j;
	struct rtpkt packet;
	
	j = rcvdpkt->sourceid;
	
	for(i=0; i<4; i++)
	{
		// se o caminho até J + o caminho até I for menor que o meu caminho minimo até I, atualiza a tabela
		if(mincost0[j] + rcvdpkt->mincost[i] < mincost0[i])
		{
			// atualiza os caminhos minimos
			mincost0[i] = mincost0[j] + rcvdpkt->mincost[i];
			// atualiza a tabela de distancia. Para ir até I atraves de J
			dt0.costs[i][j] = mincost0[i];
			change = 1;
		}
	}

	if (change)
	{
		if (TRACE>1)
		{	printf("\nTabela de distancias atualizada %d:\n", myself0);			
			printdt0(&dt0);
		}
		for (i=0; i<4; i++)
			if (i!= myself0 && i!= noway0)
			{
				packet.destid = i;
				packet.sourceid= myself0;
				for(j=0;j<4;j++) 
					packet.mincost[j] = mincost0[j];
				tolayer2(packet);
			}
	}	
}

node1.c
#include <stdio.h>
extern struct rtpkt {
  int sourceid;       /* id of sending router sending this pkt */
  int destid;         /* id of router to which pkt being sent 
                         (must be an immediate neighbor) */
  int mincost[4];    /* min cost to node 0 ... 3 */
  };

extern int TRACE;
extern int YES;
extern int NO;

int connectcosts1[4] = { 1,  0,  1, 999 };

struct distance_table 
{
  int costs[4][4];
} dt1;

// caminhos minimos
int mincost1[4];

int noway1=3;
int myself1 = 1;
	
/* students to write the following two routines, and maybe some others */

rtinit1() 
{
	int i;
	int j;

	struct rtpkt packet;

	for (i=0; i<4; i++)
		for (j=0; j<4; j++)
		{
			if (j== noway1 || i == noway1)
				dt1.costs[i][j] = connectcosts1[noway1];		// não sei o caminho
			else
			{
				if (j == myself1)
					dt1.costs[i][j]= connectcosts1[i];
				else if (i == myself1)
					dt1.costs[i][j]= 2 * connectcosts1[j];
				else if (i == j)
					dt1.costs[i][j] = connectcosts1[i];	// link direto
				else 
					dt1.costs[i][j] = connectcosts1[j]* 2 + connectcosts1[i]; // vou para j, volto para 1, e vou para i (i atraves de j)
			}
		}
	
	if (TRACE>1)
	{	printf("\nTabela de distancias inicial do nó %d:\n", myself1);
		printdt1(&dt1);
	}

	// acha os caminhos minimos
	for(j=0;j<4;j++)
		mincost1[j] = dt1.costs[j][j];

	// envia os caminhos minimos para os vizinhos;
	for (i=0; i<4; i++)
		if (i!= myself1 && i!= noway1)
		{
			packet.destid = i;
			packet.sourceid= myself1;
			for(j=0;j<4;j++) 
				packet.mincost[j] = mincost1[j];

			tolayer2(packet);
		}
}

rtupdate1(rcvdpkt)
  struct rtpkt *rcvdpkt;
  
{
	int change = 0;
	int i, j;
	struct rtpkt packet;
	
	j = rcvdpkt->sourceid;
	
	for(i=0; i<4; i++)
	{
		// se o caminho até J + o caminho até I for menor que o meu caminho minimo até I, atualiza a tabela
		if(mincost1[j] + rcvdpkt->mincost[i] < mincost1[i])
		{
			// atualiza os caminhos minimos
			mincost1[i] = mincost1[j] + rcvdpkt->mincost[i];
			// atualiza a tabela de distancia. Para ir até I atraves de J
			dt1.costs[i][j] = mincost1[i];
			change = 1;
		}
	}

				
	if (change)
	{
		if (TRACE>1)
		{	printf("\nTabela de distancias atualizada %d:\n", myself1);			
			printdt1(&dt1);
		}
		for (i=0; i<4; i++)
			if (i!= myself1 && i!= noway1)
			{
				packet.destid = i;
				packet.sourceid= myself1;
				for(j=0;j<4;j++) 
					packet.mincost[j] = mincost1[j];
				tolayer2(packet);
			}
	}
}