Saltar para o conteúdo

Vetor distância

Origem: Wikipédia, a enciclopédia livre.

Cada roteador mantém uma tabela (ou vetor) que fornece a melhor distância conhecida até cada destino; as tabelas são atualizadas através de troca de mensagens com seus roteadores vizinhos.

Pode-se representar essa rede usando um grafo [1] em que os nós correspondem aos roteadores e uma aresta entre v e w existe se os dois roteadores estiverem conectados diretamente por um link. O custo da aresta representa o atraso no link (v,w); o menor caminho é aquele que minimiza o atraso entre uma fonte s e um destino t. Para isso, podemos usar o algoritmo de Bellman-Ford,[2][1] já que ele utiliza apenas conhecimentos locais dos nós vizinhos - suponha que o nó v mantém seu valor de menor distância a t igual a M[v]; então, para atualizar esse valor, v só precisa obter o valor de M[w] de cada vizinho w e computar min (P(v,w)+M[w]) baseado nas informações obtidas, onde P(v,w) é o atraso do link entre v e w.

Entretanto, esse algoritmo pode ser melhorado de forma que se torna melhor para aplicar a roteadores e, ao mesmo tempo, um algoritmo mais rápido, na prática [3]. Em cada iteração i, cada nó v tinha que entrar em contato com cada vizinho w e "puxar" o novo valor M[w] ("pull-based implementation") [2]. Se um nó w não mudou seu valor, então não há necessidade de v pegar o valor M[w] novamente; porém, pelo algoritmo de Bellman-Ford, não tem como v saber isso e ele "puxará" esse valor de qualquer maneira [4].

Esse desperdício sugere uma "Push-based implementation", onde o valor é apenas transmitido quando sofre alguma mudança. Ou seja, cada nó w cujo valor da distância é alterado em alguma iteração informa seu novo valor a todos os vizinhos na próxima iteração [5]; isso permite que os vizinhos atualizem seus valores de acordo com a mudança que w sofreu. Se M[w] não mudou, então os vizinhos de w já tem o seu valor e não há necessidade de informá-los de novo. Essa mudança leva à poupança no tempo que o algoritmo leva para rodar, já que nem todos os valores tem que ser atualizados a cada iteração [6]. Logo, o algoritmo deve terminar mais cedo, se nenhum valor mudar durante uma iteração. [7]

O código em Python seria:

PushBasedShortestPath(G,s,t):  #G é a matriz de adjacência com peso
    n=len(G)                              #infinito em (i,j) quando não tem 
    M=[]                                    #aresta entre os nós i e j
    for node in range(n):
        M.append(float("inf"))
    M[t]=0  
    first=range(n)
    for i in range(1,n,1):
        teste=copy.deepcopy(M)
        for node in range(n):
            aux=map(sum,zip(M,G[node]))
            if M[node]>min(aux):
                for node1 in range(n):
                    for node2 in range(n):
                        M[node1]=min(M[node1],G[node1][node2]+M[node2])
                        if M[node1]>(G[node1][node2]+M[node2]):
                            first[node1]=node2
        print M
        if M==teste:
            break
    return M[s]

  1. a b Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald; Stein, Clifford (13 de janeiro de 2017). Algorithmen - Eine Einführung. [S.l.]: De Gruyter 
  2. a b Bellman, Richard (1958). «On a routing problem». Quarterly of Applied Mathematics (1): 87–90. ISSN 0033-569X. doi:10.1090/qam/102435. Consultado em 29 de setembro de 2024 
  3. Bertsekas, Dimitri P.; Gafni, Eli M.; Gallager, Robert G. (1 de março de 1981). «Second Derivative Algorithms for Minimum Delay Distributed Routing in Networks». Fort Belvoir, VA. Consultado em 29 de setembro de 2024 
  4. Hacken, George (maio de 2006). «Review of "High-Assurance Design: Architecting Secure and Reliable Enterprise Applications by Clifford Berg," Addison-Wesley Professional, 2005, $54.99, ISBN: 0321375777.». Queue (4). 50 páginas. ISSN 1542-7730. doi:10.1145/1142055.1142074. Consultado em 29 de setembro de 2024 
  5. Nagumey, Anna (dezembro de 1989). «Book Review : Parallel and Distributed Computation: Numerical Methods». The International Journal of Supercomputing Applications (4): 73–74. ISSN 0890-2720. doi:10.1177/109434208900300408. Consultado em 29 de setembro de 2024 
  6. Shah, Devavrat; Zaman, Tauhid (agosto de 2011). «Rumors in a Network: Who's the Culprit?». IEEE Transactions on Information Theory (8): 5163–5181. ISSN 0018-9448. doi:10.1109/tit.2011.2158885. Consultado em 29 de setembro de 2024 
  7. Goldberg, Andrew V.; Tarjan, Robert E. (outubro de 1988). «A new approach to the maximum-flow problem». Journal of the ACM (em inglês) (4): 921–940. ISSN 0004-5411. doi:10.1145/48014.61051. Consultado em 29 de setembro de 2024 
Ícone de esboço Este artigo sobre Tecnologia é um esboço. Você pode ajudar a Wikipédia expandindo-o.