Search

Problemas de multi-fluxo de commodities com custos não lineares e convexos surgem freqüentemente na alocação de tráfego em redes de comunicação, em função das medidas de desempenho serem baseadas principalmente em atrasos médios de transmissão devido à congestão. A rede física forma uma rede de filas aberta onde as commodities devem ser simultaneamente roteirizadas desde suas origens até seus destinos. Métodos exatos de avaliação de desempenho estão disponíveis quando os processos de chegada e serviço na rede são considerados como processos de Poisson. Nestes casos, a rede pode ser decomposta e cada arco da rede pode ser analisado separadamente como um sistema de fila M/M/1. Porém, em muitos outros casos estas hipóteses de processos de Poisson não são verificadas nas situações práticas. Métodos aproximados de decomposição têm sido desenvolvidos para avaliação do desempenho de redes de filas com distribuições de probabilidade genéricas, dado que, para estas redes, em geral não existem métodos exatos ou eles são muito difíceis de serem computados. Neste trabalho propomos um algoritmo que combina métodos de roteamento de fluxos e métodos aproximados de decomposição para tratar problemas de multi-fluxo de commodities em redes de filas abertas genéricas. Multicommodity flow problems with non-linear and convex costs often arise in traffic allocation of communication networks, as the performance measures are mainly based on average transmission delays due to congestion. The physical network forms an open queuing network where the commodities should be simultaneously routed from their origins to their destinations. Exact performance evaluation methods are available when the arrival and service processes of the network are considered as Poisson processes. In these cases, the network can be decomposed and each network arc is analyzed separately as an M/M/1 queuing system. However, in many other cases these assumptions of Poisson processes are not verified in practical situations. Approximate decomposition methods have been developed to evaluate the performance of queuing networks with general probability distributions, given that for these networks in general there are no known exact methods, or they are of difficult computation. In this work we propose an algorithm that combines multi-flow routing methods and approximate decomposition methods to deal with multicommodity flow problems in general open queuing networks.