O problema de roteamento de dados em rede de computadores consiste em minimizar o tempo médio de atraso na transmissão de mensagens, escolhendo para elas um caminho ótimo, através dos arcos da rede. Em seu trabalho, Luvezute propôs um algoritmo primai de relaxamento para otimizar o problema de roteamento de dados. O algoritmo proposto por Luvezute resolve iterativamente o problema de multifluxo, decompondo-o da forma mais independente possível, em subproblemas de simples fluxo, sendo um subproblema para cada mensagem. Esta independência entre os cálculos permite que a resolução dos subproblemas seja simultânea, admitindo-se assim uma implementação em paralelo. Nesta dissertação apresentamos um algoritmo paralelo, do tipo Fase I para encontrar uma solução inicial factível para o problema de multifluxo. Este algoritmo permite resolver de maneira mais rápida os problemas de grande porte que é o nosso objetivo inicial. O algoritmo de Fase I aqui desenvolvido pode ser utilizado para problemas de Multifluxo em geral, isto é, problemas com função objetivo linear ou não linear. O algoritmo desenvolvido foi escrito em linguagem C e implementado numa rede de microcomputadores, usando o sistema operacional UNIX. Além dos testes computacionais, apresentamos uma análise da eficiência do algoritmo e do seu speedup.

In this thesis a parallel algorithm is presented to find a feasible initial solution for the routing problem. The optimal routing in packet-switched networks consists of minimizing the medium delay time in the transmission of messages. This problem belongs to the class of multicommodity network flow problems. The developed algorithm can be used to solve multicommodity network flow problems with linear or nonlinear objective function. It solves, in fast way, problems of great size. The algorithm was written in C language and implemented in the computers network. The operating system UNIX was used. They are presented experimental results, and an analysis of the efficiency and the speedup.