RCO3-2011-2
Professor
Nome do Professor: Eraldo Silveira e Silva
email: eraldo@ifsc.edu.br
Material de Referência
Aulas
3/08/2011:
-Apresentação do Plano de Ensino
Objetivos da Aula
\item Apresentar plano de Ensino;
\item Caracterizar as funcionalidades da camada de rede;
\item Compreender a necessidade de algoritmos de roteamento para construção
dinâmica de tabelas de roteamento;
\item Comprender o funcionamento do algoritmo estado de enlace
(\textit{link-state}).
Funcionalidades da Camada de Rede
A camada de rede é, no modelo OSI, responsável por viabilizar o transporte de
pacotes, em uma rede de comutação de pacotes, desde um hospedeiro fonte até um
hospedeiro receptor, passando por vários roteadotes ao longo do caminho.
São funcionalidades da camada de rede \cite{Kurose1}:
- a determinação dos caminhos a serem seguidos pelo pacote; este é o papel
dos algoritmos/protocolos de roteamento;
- a comutação de pacotes dentro de um roteador, desde uma interface de
entrada até uma interface de saída;
- o estabelecimento de uma chamada: algumas redes necessitam do
estabelecimento do caminho (circuitos virtuais) antes de que os pacotes sejam
enviados (não é o caso da Internet).
Além disto a camada de rede pode estar envolvida com outros aspectos tais como:
- garantia de largura de banda para fluxos de pacotes;
- preservação de temporização entre pacotes (``jitter);
- entrega ordenada de pacotes de um fluxo;
- realimentação de informação sobre o congestionamento da rede.
A camada IP pode ser considerada como um subconjunto funcional da camada de
rede da OSI.
Circuitos Virtuais versus Datagramas
O circuito virtual é baseado no estabelecimento de um caminho para todos os
pacotes de um dado fluxo, antes que este fluxo seja enviado. Isto implica
que:
- um protocolo de sinalização deva ser utilizado para o estabelecimento
inicial do caminho, bem como para a manutenção e término da conexão;
- um pacote de um fluxo não necessita possuir os endereços de destino e
origem. Basta conter o identificador do circuito virtual;
- cada roteador ao longo do caminho deve manter o estado associado ao
circuito virtual; isto traz problemas de escalabilidade;
- um circuito virtual pode ter recursos associados ao mesmo: buffers em
roteadores, banda garantida etc.
São exemplos de redes baseadas em circuitos virtuais o ATM, o X.25 e o
frame-relay.
Ao contrário dos circuitos virtuais, a rede baseada em datagramas
(sem conexão) não mantém estados nos roteadores. Cada pacote traz o endereço de
destino e de fonte, de forma que podem ser enviados de forma independente. Os
roteadores encaminham os pacotes baseados no endereço de destino de forma que
dois pacotes para um mesmo destino podem seguir caminhos diferentes.
Existem vantagens e desvantagens no uso destes modelos. Enquanto nas redes com
conexão pode se ter maior qualidade de serviço, através da alocação de recursos
específicos para um fluxo, as redes sem conexão não exigem complexidade do
núcleo da rede. Este último é o modelo adotado na Internet.
Os protocolos de roteamento
Seja qual for o modelo usado, será necessário a utilização de um protocolo de
roteamento para a determinação das tabelas de encaminhamento, de forma dinâmica,
em cada roteador. Em pequenas redes estas tabelas podem ser montadas
estaticamente pelo administrador mas em redes maiores isto é inviável.
De forma abstrata, podemos representar uma rede por vértices e arestas conforme
a Fig.. Os vértices são os roteadores e as arestas os
enlaces físicos. Associados aos enlaces podem estar o custo financeiro, nível
de congestionamento etc.
O problema do protocolo de roteamento é determinar uma boa rota (sequência
de roteadores) para um determinado pacote/fluxo desde a fonte até o destino.
Esta rota deve ser repassada para as tabelas de encaminhamento dos roteadores
(chamadas de tabelas de roteamento, de forma um pouco equivocada).
Classificação dos protocolos de roteamento
Um algoritmo de roteamento pode ser classificado em centralizado ou
descentralizado. Nos algoritmos centralizados os roteadores possuem conhecimento
de toda a
topologia da rede e dos custos dos enlaces. No caso descentralizado o
roteador conhece os vizinhos diretos e os custos até eles e usa um
processo iterativo de cálculo e de troca de informações com vizinhos.
O algorimos de vetor de distância é distribuído enquanto o estado de enlace é
centralizado.
O algoritmo de estado de enlace (algoritmo de Dijkstra)
Para execução deste algoritmo o roteador deve possuir toda topologia da rede,
trasportada normalmente por difusão, através de um protocolo.
O algoritmo computa, em cada roteador, o caminho de menor custo para todos os
nós da rede, gerando as tabelas de encaminhamento para o roteador de origem.
Notação
A seguinte notação será utilizada para explanar o algoritmo:
- : vértice de origem;
- : custo do enlace do nó ao nó . O custo é infinito se não
forem vizinhos diretos;
- : valor corrente do custo do caminho da origem ao destino ;
- : nó antecessor no caminho da origem ao nó , imediatamente antes
de ;
- : conjunto de nós cujo caminho de menor custo já foi determinado.
O algoritmo é o seguinte:
\begin{verbatim}
1 Inicialização:
2 N = {A}
3 para todos os nós V
4 se V for adjacente ao nó A
5 então D(V) = c(A,V)
6 senão D(V) = infinito
7
8 Repete
9 determina W não contido em N tal que D(W) é o mínimo
10 adiciona W ao conjunto N
11 atualiza D(V) para todo V adjacente ao nó W e ainda não em N:
12 D(V) = min( D(V), D(W) + c(W,V) )
13 /* novo custo ao nó V ou é o custo velho a V ou o custo do
14 menor caminho ao nó W, mais o custo de W a V */
15 Até que todos nós estejam em N
\end{verbatim}
Exemplo: Seja a rede da Fig.
- FIGURE DELETED
A execução do algoritmo no roteador produz o seguinte resultado:
- TABLE DELETED
Exercícios
- Calcular as rotas a partir de B, para a rede da
Fig.. Qual é a tabela de roteamento de B?
- FIGURE DELETED
- Cite e explique as três funcionalidades básicas da camada de rede do
modelo OSI.
- Qual a diferença entre algoritmo de roteamento centralizado versus
distribuído?
- Cite em que classificação se enquadra o algoritmo estado de enlace.
- Pesquise e responda qual é o possível problema de oscilação do algoritmo
de Dijkstra.