O algoritmo W est first é adaptativo. Nele, os pacotes podem ser roteados inicialmente para OESTE, mas depois que o sentido NORTE, SUL ou LESTE for assumido, não é mais permitida a dire- ção OESTE. A Figura 3.11 detalha as curvas proibidas através de setas pontilhadas, ilustrando que a ocorrência de deadlock é evitada a partir da eliminação de possíveis ciclos [DAL87].
(a) (b)
Curvas proibidas Curvas permitidas
Figura 3.11 – Diagrama de curvas para o algoritmo de roteamento West first. Em (a) e em (b), nota-se que curvas para OESTE são proibidas após caminhamentos em sentido diferente de OESTE. Note-se que sempre
se pode ir inicialmente para OESTE.
Em redes que empregam topologia malha 2D, a disposição dos destinos em relação à ori- gem da comunicação assume uma das situações ilustradas na Figura 3.12. Nesta Figura, destinos identificados por X são os que se encontram no mesmo eixo X da origem da comunicação e são re- ferenciados doravante como MmoX. Diferencia-se destinos MmoX como negativos (MmoXNeg),
quando sua coordenada X é menor que da origem, ou como positivo (MmoXPos), quando sua coor-
denada X é maior que a origem. Ainda na Figura 3.12, destinos identificados por Y são os que se encontram no mesmo eixo Y da origem e são referenciado como MmoY. Diferencia-se destinos MmoY como negativos (MmoYNeg), quando sua coordenada Y é menor que a origem, ou como posi-
tivos (MmoYPos), quando sua coordenada Y é maior que a origem. Destinos identificados naquela Figura com o valor 1 encontram-se no quadrante inferior esquerdo, representando um posiciona- mento totalmente negativo em relação à origem e serão doravante classificados como no quadran- te negativo negativo (QdXNegYNeg). Destinos identificados com o valor 2 encontram-se no quadrante
superior esquerdo e serão doravante classificados como no quadrante negativo positivo (QdXNegY- Pos). Destinos identificados pelo valor 3 encontram-se no quadrante superior direito e serão dora-
vante classificados como no quadrante positivo positivo (QdXPosYPos). Destinos identificados pelo
valor 4 encontram-se no quadrante inferior direito e serão doravante referenciados como no qua- drante positivo negativo (QdXPosYNeg).
Com base nas definições de posicionamento dos destinos em relação à origem em redes malha 2D, adotam-se as seguintes características para roteamento West first. Independente da minimalidade do algoritmo, sempre que o posicionamento do destino for menor do que a origem em relação ao eixo X, os primeiros passos necessariamente terão de ser para OESTE. Isto é válido para destinos localizado em MmoXNeg, QdXNegYNeg e QdXNegYPos, conforme ilustrado na Figura
3.13(a). Outro fator a este algoritmo, independente de sua característica de minimalidade, é o ca- minhamento no sentido LESTE o qual é limitado ao eixo vertical onde se encontra o destino, sendo
proibido ultrapassá-lo, conforme ilustrado na Figura 3.13(b). 4 X Y X Y 1 2 3 Destino possível Origem
Figura 3.12 - Disposição relativa dos destinos em relação à origem da comunicação em redes malha 2D.
(a) (b)
Limite mínimo Limite máximo Destinos possíveis
Origem
Figura 3.13 – Características do roteamento com o algoritmo West first. Em (a), quando o destino encontra- se a esquerda da origem, o roteamento inicial para OESTE é obrigatório até que a coluna do destino seja
alcançada, podendo continuar para OESTE caso o algorítmo seja não mínimo. Em (b), quando o destino encontra-se à direita da origem, o caminhamento nunca pode ultrapassar a coluna do destino.
Para o algoritmo West first mínimo (wfm), o roteamento na direção OESTE é obrigatório sempre que o posicionamento do destino for negativo em relação ao eixo X da origem da comuni- cação, situação esta ilustrada na Figura 3.13(a). Neste caso e devido à minimalidade do algoritmo, quando realizado o roteamento na direção OESTE, existe somente uma rota entre o par ori- gem/destino. A Figura 3.14 (a), (b) e (c.1) representam tal condição. Outra situação em que somen- te uma rota é válida entre um par origem/destino ocorre quando o destino localiza-se em MmoX ou MmoY, conforme ilustrado na Figura 3.14 (c).
A quantidade de opções de rota entre um par origem/destino é superior a um quando o destino encontra-se em QdXPosYNeg ou QdXPosYPos em relação à origem, permitindo roteamento livre
nos sentidos NORTE, SUL e LESTE. Nestes casos, a quantidade de opções de rotas é definida pelo QE, assim como discutido para o algoritmo nfm. A Figura 3.15 ilustra as rotas permitidas para des-
tinos que se encontram em QdXPosYNeg ou QdXPosYPos em relação à origem. X-- Y + + (a) X-- Y -- (b) (c) (c.2) (c.1) (c. 3) (c. 4)
Destino Caminho válido Caminho inválido Origem
Figura 3.14 - Situações de rota única para o algoritmo wfm. Em (a) e (b) os destinos encontram-se respectivamente em QdXPosYNeg e QdXNegYNeg em relação à origem. Em (c) os destinos encontram-se sobre o
mesmo eixo X ou mesmo eixo Y em relação à origem.
(a) (b)
Destino
Origem Caminho válido
Figura 3.15 – Opções de rotas entre um par origem/destinos com distância 2 em X e 2 em Y ao adotar o algoritmo wfm. Em (a) o destino encontra-se no QdXPosYPos em relação à origem. Em (b) o destino encontra-
se em QdXPosYNeg em relação à origem. Em ambos os casos, há respeito a limites colocados de QE.
A quantidade de opções de rotas entre um par origem/destino é proporcional à distância em x e em y, conforme já definido na Equação 3.2.
Para o algoritmo West first não mínimo (wfnm), o roteamento inicial na direção OESTE também será obrigatório sempre que o posicionamento do destino for negativo em relação ao eixo X da origem da comunicação. Nos demais casos, pode-se inicialmente adotar a direção OESTE. Di- ferentemente do algoritmo wfm, no caso de obrigatoriedade de roteamento para OESTE, quando o pacote chega ao mesmo eixo Y do destino, a adoção da direção OESTE só é impedida em dois ca- sos, quais sejam: (i) uma direção que não seja OESTE já foi utilizada no roteamento do pacote ou
(ii) a borda da rede foi alcançada. A Figura 3.16 ilustra as áreas de possível roteamento quando wfnm é adotado.
(a) (b) Área de roteamento livre
Área de roteamento exclusivo para OESTE Área proibida de roteamento
Destino Origem
Figura 3.16 - Áreas de roteamento para o algoritmo wfnm. Em (a), o destino encontra-se no QdXNegYNeg em relação à origem, o que reduz a área de roteamento livre. Em (b), o destino encontra-se no QdXPosYNeg em
relação à origem, aumentando a área de roteamento livre.