Ansvarliggjøring av ansatte på alle nivå?

os n´os interm´edios, que v˜ao definindo os next hops para os pacotes at´e que estes alcancem o destino.

3.3

Algoritmo de encaminhamento Distance-Vector

O algoritmo de encaminhamento Distance-Vector (DV), tamb´em conhecido

como algoritmo de Bellman-Ford ou de Ford-Fulkerson, ´e um algoritmo que pode

ser classificado quanto a localiza¸c˜ao como distribu´ıdo e pertence a categoria dos al- goritmos orientados ao utilizador usado por diversos protocolos de encaminhamento [Thomas, 2006]. Quanto ao tipo e decis˜ao de encaminhamento ´e um algoritmo est´atico e hop-by-hop, respectivamente.

Neste algoritmo os n´os trocam informa¸c˜oes com os seus vizinhos acerca dos custos, sem conhecimentos da forma como estes determinam esses custos, convergindo para uma situa¸c˜ao em que cada n´o conhece o caminho mais curto (crit´erio de menor custo) para todos os n´os da rede. Trata-se de um algoritmo ass´ıncrono, pois as mensagens trocadas entre cada n´o e os seus vizinhos, n˜ao s˜ao feitas simultaneamente. O DV ´e uma algoritmo iterativo, pois o processo de convergˆencia, relativo `a constru¸c˜ao das tabelas de encaminhamento para cada n´o da rede, ´e feito em v´arios passos, at´e que cada n´o conhe¸ca toda a informa¸c˜ao de encaminhamento da rede.

No algoritmo de encaminhamento DV cada n´o mant´em uma tabela dos custos para os n´os vizinhos, que s˜ao actualizadas com uma certa periodicidade.

Para exemplificar o funcionamento deste algoritmo, consideremos a rede repre- sentada na Figura 3.1 e vejamos como poder´a ser calculado o caminho mais curto entre os n´os A e F . Para tal, vamos introduzir as seguintes nota¸c˜oes:

• dik custo da liga¸c˜ao entre o n´o i e o n´o vizinho k ;

CAP´ITULO 3. ALGORITMOS DE ENCAMINHAMENTO

• Dkj custo m´ınimo (k, j) do caminho entre o n´o k e j.

O Custo m´ınimo (i, j) ´e calculado de forma iteractiva de acordo com a express˜ao:

Dij = min

(k∈Ni∧ k6=i ∧ i6=j)

{dik+ Dkj}, (3.1)

onde Ni ´e o conjunto de n´os vizinhos do n´o i.

Consideremos ainda que os custos entre cada par de n´os adjacentes s˜ao: dAB =

dBA = 1, dAD = dDA = 2, dAC = dCA = 1, dBC = dCB = 1, dBD = dDB = 3,

dCE = dEC = 1, dDE = dED = 2, dCF = dF C = 5, e dEF = dF E = 1 (Figura 3.1).

Figura 3.1: Rede com 6 n´os, 9 liga¸c˜oes e os respectivos custos.

Considerando que no instante 0, nenhum n´o da rede recebeu mensagens dos custos por parte dos n´os vizinhos. Neste instante, os custos Dkj = ∞, excepto nos

casos em que o n´o vizinho ´e o n´o de destino (j = F sendo DF F = 0).

Os custos m´ınimos para o n´o F , nos diversos n´os da rede s˜ao calculadas de acordo com a express˜ao (3.1), obtendo-se os valores presentes na Tabela 3.1. Pelo

3.3. ALGORITMO DE ENCAMINHAMENTO DISTANCE-VECTOR

Tabela 3.1: C´alculo das custos dos n´os A,B,C,D e E para F, no instante in´ıcial (instante 0 ).

c´alculo, vemos que neste instante o n´o A n˜ao tem o caminho para o n´o F (pois DAF = ∞). Nota-se que os n´os C e E possuem o caminho para o n´o F pois este

´

e vizinho daqueles. Ap´os a primeira troca de mensagens, os n´os A, B e E passam

a saber que C possui um caminho para F , uma vez que o DCF 6= ∞. Da mesma

forma, os n´os C e D tamb´em passam a saber que E possui um caminho para F , pois o DEF 6= ∞. Assim, no instante 1 s˜ao calculados os novos custos para o n´o F a

partir de cada n´o da rede, com base na informa¸c˜ao dispon´ıvel em cada n´o, tal como apresentado na Tabela 3.2.

Tabela 3.2: C´alculo dos custos dos n´os A,B,C,D e E para F, no instante 1.

Nesta itera¸c˜ao e resulado da simplicidade da rede, todos os n´os da rede passam

CAP´ITULO 3. ALGORITMOS DE ENCAMINHAMENTO

a ter um caminho para o n´o F . Comparando as Tabelas 3.1 e 3.2 notamos que

inicialmente (instante 0), o n´o C possu´ıa um caminho para o n´o F com um custo de 5 (Caminho C − F ). Neste instante surge a possibilidade de alcan¸car o n´o F atrav´es do E (a partir do C) com um custo menor que o anterior. No instante 2 (Tabela 3.3), calculam-se novamente os custos m´ınimas para o n´o F , a partir de cada n´o da rede.

Tabela 3.3: C´alculo dos custos dos n´os A, B, C, D e E para F, no instante 2.

Este c´alculo conduz `a escolha de um novo caminho entre A e F que possui um menor custo, se comparado com o calculado no instante 1.

No instante 3, efectuam-se novamente os c´alculos dos custos m´ınimos para F (Tabela 3.4).

Tabela 3.4: C´alculo dos custos dos n´os A,B,C,D e E para F, no instante 3.

3.3. ALGORITMO DE ENCAMINHAMENTO DISTANCE-VECTOR

Estes c´alculos n˜ao alteram os custos obtidas na Tabela 3.3. Em conformidade com o que foi dito no inicio desta sec¸c˜ao, esta tabela ´e actualizada periodicamente, conduzindo `a um c´alculo, dos custos, a tender para o infinito. Assim, se os custos dik se mantiverem constantes e n˜ao houver altera¸c˜ao na topologia da rede (quebra de

liga¸c˜ao ou entrada dum novo n´o na rede), qualquer troca de mensagem bem como qualquer c´alculo dos custos m´ınimos para F n˜ao alterar´a os resultados da Tabela 3.4 [Kaufmann, 2007].

O exemplo anterior mostrou-nos como ´e feita a constru¸c˜ao das tabelas de enca- minhamento no algoritmo DV atrav´es dos custos (Dkj).

O algoritmo 1 apresenta os passos essenciais do processo descrito. Algoritmo 1 Pseudoc´odigo do algoritmo Distance-Vector

1: Dkj(t = 0) ⇐ ∞ {i-n´o de origem, j-n´o de destino}

2: Djj(t = 0) ⇐ 0; {t-instante de tempo}

3: {ciclo infinito} 4: while t > 0 do

5: for j = 1 to N do

6: Dij ⇐ min(k∈Ni∧ k6=i ∧ i6=j){dik + Dkj} {N-n´umero de n´os da rede e Ni ´e o

conjunto de n´os vizinhos do n´o i}

7: Dkj ⇐ Dij

8: end for

9: end while

Um factor a levar em considera¸c˜ao no algoritmo DV ´e o facto de cada n´o da rede conhecer apenas o custo para os seus vizinhos (pois os outros custos s˜ao transmitidos pelos vizinhos) e n˜ao de todo o caminho por onde deve seguir o pacote na rede para alcan¸car um dado destino. A grande vantagem deste algoritmo ´e a sua facilidade de implementa¸c˜ao, sendo muito ´uteis em redes bastante pequenas. Os protocolos

de encaminhamento mais populares que usam estes algoritmos s˜ao o RIP e o BGP

[Thomas, 2006].

CAP´ITULO 3. ALGORITMOS DE ENCAMINHAMENTO