estabelecimento; 2.3.25(b) após o estabelecimento da conexão e, 2.3.

25(c), após o envio de

três pacotes de dados.

usu ário usu ário usuário usuário u suário usuá rio

1 2 1 2 1 2

NSAPs N SA Ps NSAPs

cama da Re de ca mada R ed e ca ma da R ed e

(a) (b ) (c)

Figura 2.3.25 - Modelo de uma conexão de Rede: (a) antes do estabelecimento; (b) após o
estabelecimento; (c) após o envio de três pacotes (de 1 para 2).

b) As primitivas de serviço

A tabela a seguir apresenta as primitivas de serviço disponíveis pela camada de Rede

do modelo OSI, tanto para os serviços orientados à conexão como para os sem conexão.

SERVIÇO ORIENTADO À CONEXÃO

N_CONNECT.request(called, calling,acks_wanted,exp_wanted,qos,user_data)
N_CONNECT.indication(called,calling,acks_wanted,exp_wanted,qos,user_data)
N_CONNECT.response(responder,acks_wanted,exp_wanted,qos,user_data)
N_CONNECT.confirm(responder,acks_wanted,exp_wanted,qos,user_data)
N_DISCONNECT.request (source, reason, user_data, responding_address)
N_DISCONNECT.indication (source, reason, user_data, responding_address)
N_DATA.request (user_data)
N_DATA.indication (user_data)
N_DATA_ACKNOWLEDGE.request ( )
N_DATA_ACKNOWLEDGE.indication ( )
N_EXPEDITED_DATA.request (user_data)
N_EXPEDITED_DATA.indication (user_data)
N_RESET.request (source, reason)
N_RESET.indication (source, reason)
N_RESET.response ( )
N_RESET.confirm ( )
SERVIÇO SEM CONEXÃO
N_UNITDATA.request (source_address,dest_address, qos, user_data)
N_UNITDATA.indication (source_address,dest_address, qos, user_data)

71
N_FACILITY.request (qos)
N_FACILITY.indication (dest_address, qos, reason)
N_REPORT.indication (dest_address, qos, reason)

N_CONNECT.request é a primitiva utilizada para requisitar o estabelecimento de uma

conexão de Rede e através de seus parâmetros deve-se indicar o endereço ao qual se deseja
conectar (calling), assim como o endereço do iniciador (called). Encontra-se, ainda, nos seus
parâmetros, duas variáveis booleanas que permitem requisitar serviços adicionais.
O parâmetro acks_wanted permite indicar o pedido de reconhecimento de pacotes. Se
a camada de Rede não permite o fornecimento de reconhecimento, o fornecedor vai colocar
esta variável a falso na primitiva de indicação; da mesma forma, se a entidade destinatária não
pode fornecer reconhecimento, ela mesma o fará (colocar acks_wanted a falso) na primitiva
de resposta.
O outro parâmetro booleano, exp_wanted, permite a utilização de serviços de dados
expressos (ou urgentes), o que significa que um pacote pode violar a ordem normal dos
pacotes na fila para se colocar na cabeça desta. Isto permite, de certo modo, estabelecer um
nível de prioridade entre as mensagens a nível de Rede.
O parâmetro qos (quality of service) permite determinar a qualidade do serviço a ser
oferecido, sendo composto de duas listas de valores. A primeira lista contém o contexto
desejado pela entidade iniciadora; a segunda indica os valores mínimos aceitáveis. Se o
serviço de Rede é incapaz de fornecer pelo menos os valores mínimos estabelecidos pelo
usuário iniciador, a conexão não será estabelecida. Os valores estabelecidos neste parâmetro
são a taxa de erro, a taxa de transmissão, a confidencialidade e custo da transmissão.
O iniciador pode, através do parâmetro user_data, introduzir dados no pedido de
conexão, podendo a entidade chamada consultar estes dados antes da aceitação da conexão.
A aceitação de uma conexão é feita pelo chamador através da primitiva
N_CONNECT.indication; por outro lado, a recusa é implementada através da primitiva
N_DISCONNECT.request, que informa, através do parâmetro reason, o motivo do não
estabelecimento da conexão.
Se a conexão é estabelecida, a transmissão de dados é feita utilizando a primitiva
N_DATA.request, que será refletida no receptor por uma primitiva N_DATA.indication. Caso
um pedido de reconhecimento de pacotes foi acertado entre os usuários da camada no
momento da conexão, o reconhecimento será implementado através do envio, pelo receptor,
de uma primitiva N_DATA_ACKNOWLEDGE.request.
As primitivas N_RESET são utilizadas para sinalizar problemas de comunicação, tais
como o bloqueio de uma entidade de transporte envolvida na comunicação ou mesmo do
fornecedor do serviço. O efeito deste serviço é o esvaziamento das filas de espera, sendo que

72
as informações presentes nestas serão perdidas. As perdas deverão ser recuperadas pela
camada de Transporte.
As primitivas N_UNITDATA são utilizadas para o envio de dados no serviço sem
conexão; elas não oferecem nem controle de erros nem de fluxo. N_FACILITY é o serviço que
permite ao usuário obter informações sobre as características da transmissão de informação,
por exemplo, a percentagem de pacotes distribuídos.
Finalmente, a primitiva N_REPORT permite à camada de Rede informar a ocorrência
de problemas relativos ao serviço de Rede, como, por exemplo, a indisponibilidade
momentânea de um determinado endereço destinatário.

c) O endereçamento de Rede
Uma função importante desta camada é o fornecimento de uma codificação espacial de
endereços coerente para uso da camada de Transporte. O fato é que, para cada rede, foi
definida uma estrutura distinta de endereçamento, o trabalho de uniformização ficando a cargo
da camada de Rede.
De uma forma geral, 2 esquemas básicos de endereçamento são possíveis:
• endereçamento hierárquico: o endereço é constituído conforme a posição de cada
entidade na hierarquia da rede, sugerindo o local onde esta se encontra. Este
esquema de endereçamento é usado em WANs e MANs (ex.: Internet). Esta técnica
facilita o roteamento.
• endereçamento horizontal: aqui, o endereço não tem relação com localização da
entidade na rede. Este esquema é usado em LANs (ex.: padrão IEEE 802). Este tipo
de técnica facilita a reconfiguração da rede sem necessitar alterar os endereços das
estações.

No modelo OSI, a estrutura de endereçamento a nível de Rede foi concebida de modo

a incorporar as características das diversas estruturas de endereçamento existentes. Todas as
primitivas de serviço de Rede utilizam o endereçamento orientado aos NSAPs para identificar
a origem ou o destinatário de um pacote. A figura 2.3.26 mostra o formato do endereço de
NSAP, que é composto de três campos:

• AFI (Authority and Format Identifier), identifica o tipo de endereçamento existente

no terceiro campo do endereço, possibilitando uma numeração entre 10 e 99,
correspondente aos diferentes formatos existentes e deixando ainda possibilidades
de extensão;
• IDI (Initial Domain Identifier) indica o domínio ao qual pertence o número do DSP
(o terceiro campo) — se o DSP é um número de telefone, este campo indicará o
código do país;

73
 • DSP (Domain Specific Part) contém o endereço específico do NSAP no domínio
considerado.

AFI IDI DSP

IDP

Figura 2.3.26 - Endereçamento de um NSAP.

[Link]. A função de Roteamento

Como dito na parte introdutória, a função principal da camada de Rede é efetuar o

encaminhamento dos pacotes trocados entre duas entidades oferecendo uma comunicação
fim-a-fim. Durante a trajetória os pacotes sofrerão uma série de saltos, sendo que a decisão de
que caminho utilizar é feita a nível da camada de Rede. Esta decisão pode levar em conta (ou
não) a situação da rede do ponto de vista do tráfego de informação.
Num primeiro ponto, dado este último aspecto, pode-se distinguir os diferentes
algoritmos de roteamento em duas principais classes: os algoritmos adaptativos e não
adaptativos. Os algoritmos não adaptativos não levam em conta a situação de tráfego da rede,
fazendo o denominado roteamento estático; já os adaptativos o fazem considerando
modificações de topologia da rede e do tráfego real.
As seções que seguem vão discutir alguns dos conjuntos de algoritmos de roteamento
existentes.

a) Algoritmo do caminho mais curto

Este algoritmo é baseado numa representação da subrede na forma de um grafo, onde

os nós são os IMPs e os arcos são as linhas de comunicação. A escolha de uma trajetória é,
então, baseada neste grafo, o objetivo sendo encontrar o caminho mais curto entre dois IMPs.
O conceito de caminho mais curto pode levar em conta diferentes aspectos:

• o número de nós entre os dois pontos;

• a distância geográfica entre os pontos;
• os tempos de espera em cada nó da trajetória, etc...

No terceiro caso, por exemplo, os arcos são etiquetados com um valor que representa o
tempo médio de espera entre o envio e a recepção de um pacote de teste, expedido
periodicamente.

74
 Um exemplo de algoritmo do caminho mais curto é aquele definido por Dijkstra, onde
cada nó é etiquetado pela distância do nó fonte seguindo o caminho mais curto conhecido.
Como, inicialmente, nenhum caminho é conhecido, os nós são etiquetados com «infinito», ou
" ". Estas vão sendo atualizadas à medida que o algoritmo progride e que os caminhos vão se
tornando conhecidos, as etiquetas vão indo do provisório ao permanente uma vez que o
caminho mais curto foi encontrado para os diferentes nós.
A figura 2.3.27 ilustra o funcionamento deste algoritmo. Vamos considerar o grafo
apresentado em 2.3.27(a), onde os arcos são etiquetados com o valor da distância entre os nós.
Vamos considerar que o objetivo aqui é encontrar o caminho mais curto entre A e D.
Como o nó A é o nó de origem, ele será marcado por um nó de referência (fundo cinza)
e serão analisados os nós adjacentes. Estes serão etiquetados pela distância que os separa de A,
marcando também, na etiqueta, o último nó a partir do qual o cálculo foi feito. Após a análise
dos nós adjacentes a A, marca-se aquele contendo a etiqueta de menor valor, como mostrado
em 2.3.27(b), este nó passando a ser o nó ativo (ou de referência).
Repetindo a análise para o nó B, define-se o nó E como sendo o novo nó ativo,
mostrado em 2.3.27(c). O algoritmo vai progredindo até que o caminho mais curto seja então
encontrado, as etiquetas sendo modificadas segundo as análises efetuadas. A progressão do
algoritmo para o exemplo é ilustrada por 2.3.27(d), 2.3.27(e) e 2.3.27(f).
Para este exemplo, o caminho mais curto fica sendo pelas estações A-B-E-F-H-D,
sendo A a origem e D o destino final.

B 7
C B (2,A) C ( ,-)

2 2 3 3
E ( ,-)
2
A E F D A F ( ,-) D ( ,-)

6 1 2 2
4

G H G (6,A) H ( ,-)
(a) (b)

B (2,A) C (9,B) B (2,A) C (9,B)

E (4,B) E (4,B)
A F ( ,-) D ( ,-) A F (6,E) D ( ,-)

G (6,A) H ( ,-) G (5,E) H ( ,-)

(c) (d)

B (2,A) C (9,B) B (2,A) C (9,B)

E (4,B) E (4,B)
A F (6,E) D ( ,-) A F (6,E) D ( ,-)
Final = D (10,H)

G (5,E) H (9,G) G (5,E) H (8,F)

(e) (f)

Figura 2.3.27 - Ilustração do algoritmo de Dijkstra.

75
 O algoritmo do caminho mais curto pode ser executado localmente em cada nó,
partindo de uma informação fixa sobre os custos de cada linha (roteamento estático
distribuído).
O algoritmo pode também ser executado por uma estação encarregada de definir rotas
entre todos os demais nós. Esta estação é chamada RCC (Routing Control Center). A RCC
recebe novos dados sobre custo de certas linhas cada vez que uma mudança ocorre
(roteamento dinâmico centralizado). O uso da RCC pode causar sobrecarga na rede se
ocorrem alterações muito freqüentes nos custos de cada linha, pois a RCC tem que receber
muitas mensagens contendo novos dados sobre custos das linhas afetadas.

b) Roteamento multicaminhos

Este algoritmo leva em conta a possibilidade de existência de diversos caminhos entre

dois nós de valores quase equivalentes. Desta forma, o desempenho da rede pode ser
melhorado, se o tráfego é assumido por vários caminhos, reduzindo assim a carga de uma
dada linha de comunicação.
Esta técnica de roteamento é implantada da seguinte forma: cada IMP mantém
atualizada uma tabela com uma linha para cada IMP da rede. Para cada IMP, tem-se as
diferentes linhas de saída para este destino, classificadas em ordem decrescente, do melhor ao
menos eficiente, com um peso relativo.
Antes do envio de um pacote, o IMP gera um número aleatório para definir o caminho,
utilizando os pesos como probabilidade. As tabelas são criadas de maneira estática pelo
administrador do sistema e carregadas em cada IMP na inicialização da rede.
O grafo da figura 2.3.28(a) ilustra o desenvolvimento deste algoritmo, sendo que em
2.3.28(b) está apresentada a tabela para o IMP J. Se J recebe um pacote destinado a A, ele
pode optar por um dos três caminhos, consultando a tabela na linha associada ao nó A.
A primeira escolha é o caminho direto a A, as outras sendo via I e H, respectivamente.
A decisão é, então, baseada na geração de um número aleatório entre 0,00 e 0,99. Se o número
é inferior a 0,63, a linha A será escolhida, se estiver entre 0,63 e 0,83, a linha passando por I
será escolhida; senão, será a linha que passa por H.

76
 A A 0,63 I 0,21 H 0,16
A B B A 0,46 H 0,31 I 0,23
C D
C A 0,34 I 0,33 H 0,33
D H 0,50 A 0,25 I 0,25
E A 0,40 I 0,40 H 0,20
E F G H F A 0,34 H 0,33 I 0,33
G H 0,46 A 0,31 K 0,23
H H 0,63 K 0,21 A 0,16
I I 0,65 A 0,22 H 0,13
· · · · · · ·
I J K L K K 0,67 H 0,22 A 0,11
L K 0,42 H 0,42 A 0,16

(a) (b)

Figura 2.3.28 - Ilustração do algoritmo multicaminho: (a) grafo da rede; (b) tabela p/ nó J.

A vantagem desta técnica sobre a anterior é a possibilidade de definir diferentes

classes de tráfego sobre diferentes caminhos. Uma outra vantagem é a confiabilidade, uma vez
que várias linhas podem ser perdidas sem que a rede perca a sua conectividade.

c) Roteamento dinâmico distribuído

Nesta técnica, cada estação troca periodicamente informações de roteamento com suas
vizinhas. Cada estação envia aos seus vizinhos imediatos uma tabela contendo informação
sobre custo de transmissão a partir dela para cada uma das demais estações da rede. Esta
tabela contém, para cada destino possível, o nó preferencial de saída e o custo estimado de
transmissão por este nó. Este tipo de roteamento também é conhecido como Roteamento por
Vetor de Distancia (Distance Vector Routing).
Cada nó tem que conhecer o custo de transmissão para cada um dos seus vizinhos
imediatos. Para decidir a rota, a estação emissora soma o custo de transmissão até o vizinho
imediato com custo estimado dali até destino final.
A operação deste tipo de algoritmo é ilustrada na figura 2.3.29.

77
 local
recebido das demais estações

Origens nova
A I H K J tabela J
A 0 24 20 21 8 8 A
A B C D B 12 36 31 28 - 20 A
C 25 18 19 36 - 28 I
d
e D 40 27 8 24 - 20 H
E F G H s E 14 7 30 22 - 17 I
t F 23 20 19 40 - 30 I
i G 18 31 6 31 - 18 H
n H 17 20 0 19 12 12 H
o
s I 21 0 14 22 10 10 I
I J K J 9 11 7 10 0 0 -
L
K 24 22 22 0 6 6 K
L 29 33 9 9 - 15 K
(a) subrede (b) tabelas do nó J

Figura 2.3.29 - Roteamento dinâmico distribuído

No exemplo acima, uma mensagem do nó J para o nó B será roteada através do nó A,

enquanto uma mensagem destinada ao nó C passará pelo nó I (ver última tabela a direita, na
figura 2.3.39). Vale lembrar que esta escolha de rota pode mudar, pois o roteamento é
dinâmico, isto é, as tabelas são periodicamente atualizadas. Um algoritmo baseado neste
principio, denominado RIP (Routing Information Protocol) foi implementado originalmente
na ARPANET e posteriormente na Internet (parte do protocolo IP até 1990, quando foi
substituido pelo protocolo OSPF, Open Shortest Path First), e na rede novell (protocolo IPX).

[Link]. O controle de congestionamento

Durante o funcionamento de uma aplicação distribuída construída sobre uma rede, vão
existir instantes em que o fluxo de mensagens sendo trocadas pode atingir valores bastante
importantes, de tal forma que os nós intermediários, responsáveis do tratamento dos pacotes,
não sejam mais capazes de tratar os pacotes para retransmissão. Isto, naturalmente, vai ter
como conseqüência uma degradação no funcionamento da rede, podendo trazer prejuízos
(lentidão, perdas de pacotes) ao desempenho da aplicação e comprometendo o seu correto
funcionamento. As causas desta sobrecarga, conhecida por congestionamento, podem ser de
várias naturezas. Um exemplo disto pode ser a lentidão dos nós na realização do roteamento
ou um mau funcionamento do mecanismos de controle de fluxo.
O congestionamento consiste, normalmente de um processo a realimentação positiva,
o número de mensagens tendendo a crescer se a rede está congestionada.

78
 Sendo assim, a camada de Rede deve também fazer este papel, através da
implementação de funções de controle de congestionamento, alguns dos quais serão descritos
a seguir.

a) Pré-alocação de buffers
Uma primeira forma de controlar o congestionamento da rede é através da pré-
alocação de buffers, particularmente se o serviço é orientado à conexão. Isto significa que, no
momento do estabelecimento do circuito virtual que vai caracterizar a conexão, um
determinado número de buffers deve ser alocado em cada nó para permitir o armazenamento
dos pacotes a serem retransmitidos. Evidentemente, o número de buffers a ser alocado vai
depender do protocolo implementado entre cada par de nós intermediários (IMPs). Um
algoritmo do tipo “envia-espera” vai exigir um número de buffers evidentemente menor do
que um algoritmo que autorize o envio de diversos pacotes antes da retransmissão.

b) A destruição de pacotes

Um outro mecanismo que é adotado para o controle de congestão é o da destruição de

pacotes. Neste caso, não existe reserva prévia de buffers, de modo que, se um pacote chega
num IMP e este não dispõe de buffer para o seu armazenamento, este é simplesmente
destruído (ou descartado). Se o serviço oferecido é do tipo “datagrama”, não há mais nada a
fazer; por outro lado, se este é orientado à conexão, o pacote deverá ser armazenado em algum
nó para uma possível retransmissão. Ainda, a destruição de pacotes deve seguir uma certa
disciplina: por exemplo, destruir um pacote de reconhecimento pode não ser uma boa solução,
uma vez que este pacote poderia permitir ao nó o apagamento de um pacote de informação e,
por conseqüência, a liberação de um buffer. Uma solução para isto é a reserva, para cada linha
de chegada, de um buffer que possibilite a recepção de pacotes de reconhecimento
endereçados àquele nó.

c) O controle de fluxo
O controle de fluxo consiste em outra técnica de controle de congestionamento,
embora não muito eficiente nesta tarefa. O problema do controle do fluxo é o fato que os
limites do tráfego não podem ser estabelecidos a valores muito baixos, pois isto pode
provocar problemas de eficiência na aplicação se um pico de tráfego é requerido. Por outro
lado, a escolha de um limite alto de tráfego pode resultar num controle medíocre do
congestionamento.

79
 d) outras técnicas

Outras técnicas de controle de congestão podem ser ainda implementadas, como por
exemplo:

• o controle isarítmico, baseado na existência em cada nó de um certo número de

fichas. O nó que tiver um pacote a transmitir, deve obter uma ficha, se existir
alguma disponível. Isto permite manter constante o número de pacotes em
circulação na rede;

• os pacotes de estrangulamento, enviados por um nó ao usuário do serviço de rede,

indicando que determinadas linhas de saída estão no limite da saturação. Isto faz
com que o usuário reduza o envio de pacotes para o destino utilizando aquela linha
até que a situação retome a normalidade.

[Link]. Exemplos de Protocolos de Rede

a) Protocolo X.25 PLP

O protocolo X.25 PLP (Packet Layer Protocol) é o protocolo de nível 3 largamente

adotado no modelo OSI fazendo parte do padrão X.25. O X.25 é o resultado dos esforços
efetuados a partir de 1974 pelo CCITT para a definição de um padrão de comunicação para os
níveis Físico, Enlace e Rede.
O X.25 define a interface entre um DTE (Data Terminal Equipment) e um DCE (Data
Circuit-terminating Equipment). Um nó intermediário da subrede (um IMP, na terminologia
OSI) é definido aqui como um DSE (Data Switching Exchange).
O padrão X.25 define o formato e o significado da informação trocada através da
interface DTE-DCE para as camadas 1, 2 e 3. No que diz respeito ao nível 1, X.25 faz
referência a outros padrões, no caso o X.21 para as transmissões digitais e X.21bis, uma versão
«analógica» do X.21, bastante similar a RS-232-C.
Na camada 2, X.25 define protocolos de enlace com o objetivo de oferecer um meio de
transmissão confiável, definindo protocolos como LAP e LAPB.
No nível de Rede, X.25 implementa as conexões entre dois DTEs (figura 2.3.29),
oferecendo dois tipos de conexão:

80