Algoritmos LS

1. Identificar os roteadores que estão fisicamente conectados a ele e receber seus endereços IP.
   Quando um roteador inicia seu trabalho, ele envia, primeiramente, um pacote com um "ALO" para a rede. Cada roteador que recebe este pacote responde com uma mensagem que contém seu endereço de IP.

2. Medir o tempo de atraso (ou quaisquer outros parâmetros importantes da rede, como média de tráfego) para roteadores vizinhos. Para poder fazer isto, os roteadores enviam pacotes de eco pela rede. Todos os roteadores que recebem estes pacotes respondem com um pacote de resposta. Dividindo o tempo de percurso por 2, os roteadores podem contar o tempo de atraso (tempo de percurso é a medida do atraso na rede, encontrado pelo tempo que um pacote de dados ricocheteou em algum host remoto). Perceba que este tempo inclui tanto o tempo de transmissão como o tempo de processamento. O tempo que leva o pacote a atingir o seu destino e o tempo que leva o receptor para processá-lo e responder.

3. Transmitir suas informações pela rede para outros roteadores e receber as informações dos outros roteadores.
   Nesta etapa, todos os roteadores compartilham seu conhecimento e transmitem suas informações uns aos outros. Desta forma, cada roteador pode conhecer a estrutura e o estado da rede.

4. Usando-se um algoritmo apropriado, identifica-se a melhor rota entre dois nós da rede.
   Nesta etapa, os roteadores escolhem o melhor caminho para cada nó. Eles fazem isto usando um algoritmo, como o algoritmo de menor caminho de Dijkstra. Neste algoritmo, um roteador, com base nas informações colhidas de outros roteadores, constrói um grafo da rede. Este grafo mostra a localização dos roteadores na rede e suas ligações uns com os outros. Cada enlace é rotulado com um número chamado peso ou custo. Este número é uma relação entre o tempo de atraso, média do tráfego e ocasionalmente o simples número de saltos entre os nós. Por exemplo, se houver duas ligações entre um nó e um destino, o roteador escolhe a ligação com menor peso.

O algoritmo de Dijkstra segue estas etapas:

1. o roteador constrói um grafo da rede e identifica os nós da fonte e do destino, como V1 e V2, por exemplo. Então ele contrói uma matriz, chamada de "matriz de adjacência". Nesta matriz, a coordenada indica o peso. Por exemplo, [i, j] é o peso de uma ligação ente Vi e Vj. Se não houver uma ligação direta entre Vi e Vj, este peso é identificado como "infinito";

2. o roteador constrói um conjunto de registros de estado para cada nó da rede. O registro contém três campos:
   • campo do predecessor - o primeiro campo mostra o nó prévio
   • campo do comprimento - o segundo campo mostra a soma dos pesos do nó na frente a esse nó 
   • campo do rótulo - o último campo mostra o estado do nó. Cada nó pode ter um estado: "permanente" ou "tentativa"

3. o roteador inicializa os parâmetros do conjunto do registro de estado (para todos os nós) e coloca seus tamanhos como "infinito" e seu rótulo como "tentativa";

4. o roteador posiciona um T-node. Por exemplo, se V1 deve ser o T-node fonte, o roteador modifica o rótulo de V1 para "permanente". Quando um rótulo muda para "permanente", ele jamais se modificará outra vez. Um T-node é apenas um agente e nada mais;

5. o roteador atualiza o conjunto de registros de estado de todos os nós tentativa que estão diretamente ligados ao T-node fonte;

6. o roteador olha para todos os nós "tentativa" e escolhe aquele cujo peso para V1 é menor. Aquele nó é então o T-node de destino;

7. se este nó não é V2 (o destino desejado), o roteador volta à etapa 5;

8. se este nó é V2, o roteador extrai seu nó prévio do conjunto de registros de estado, fazendo isto até alcançar V1. Esta lista de nós mostra o melhor caminho de V1 para V2.

Estas etapas são mostradas abaixo como um fluxograma.

Usaremos este algoritmo como um exemplo na próxima página.