RCO3-2011-2

Professor

Nome do Professor: Eraldo Silveira e Silva

email: eraldo@ifsc.edu.br

Material de Referência

• Plano da disciplina

Aulas

3/08/2011:

-Apresentação do Plano de Ensino

• A Internet

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}:

1. a determinação dos caminhos a serem seguidos pelo pacote; este é o papel

dos algoritmos/protocolos de roteamento;

1. a comutação de pacotes dentro de um roteador, desde uma interface de

entrada até uma interface de saída;

1. 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:

1. garantia de largura de banda para fluxos de pacotes;

1. preservação de temporização entre pacotes (``jitter);

1. entrega ordenada de pacotes de um fluxo;

1. 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:

1. 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;

1. um pacote de um fluxo não necessita possuir os endereços de destino e

origem. Basta conter o identificador do circuito virtual;

1. cada roteador ao longo do caminho deve manter o estado associado ao

circuito virtual; isto traz problemas de escalabilidade;

1. 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:

1. $\textstyle A$: vértice de origem;

1. $\textstyle c(i,j)$: custo do enlace do nó $\textstyle i$ ao nó $\textstyle j$. O custo é infinito se não

forem vizinhos diretos;

1. $\textstyle D(V)$: valor corrente do custo do caminho da origem ao destino $\textstyle V$;

1. $\textstyle p(V)$: nó antecessor no caminho da origem ao nó $\textstyle V$, imediatamente antes

de $\textstyle V$;

1. $\textstyle N$: 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

1. Calcular as rotas a partir de B, para a rede da

Fig.. Qual é a tabela de roteamento de B?

FIGURE DELETED

1. Cite e explique as três funcionalidades básicas da camada de rede do

modelo OSI.

1. Qual a diferença entre algoritmo de roteamento centralizado versus

distribuído?

1. Cite em que classificação se enquadra o algoritmo estado de enlace.

1. Pesquise e responda qual é o possível problema de oscilação do algoritmo

de Dijkstra.