QoS-based cooperative algorithm for integral multi-commodity flow problem

By: Mehdi Ghatee

Published: Computer Communications, Volume 34, Issue 7, 16 May 2011, Pages 835-846


This paper treats with integral multi-commodity flow through a network. To enhance the Quality of Service (QoS) for channels, it is necessary to minimize delay and congestion. Decreasing the end-to-end delay and consumption of bandwidth across channels are dependent and may be considered in very complex mathematical equations. To capture with this problem, a multi-commodity flow model is introduced whose targets are minimizing delay and congestion in one model. The flow through the network such as packets, also needs to get integral values. A model covering these concepts, is NP-hard while it is very important to find transmission strategies in real-time. For this aim, we extend a cooperative algorithm including traditional mathematical programming such as path enumeration and a meta-heuristic algorithm such as genetic algorithm. To find integral solution satisfying demands of nodes, we generalize a hybrid genetic algorithm to assign the integral commodities where they are needed. In this hybrid algorithm, we use feasible encoding and try to keep feasibility of chromosomes over iterations. By considering some random networks, we show that the proposed algorithm yields reasonable results in a few number of iterations. Also, because this algorithm can be applied in a wide range of objective functions in terms of delay and congestion, it is possible to find some routs for each commodity with high QoS. Due to these outcomes, the presented model and algorithm can be utilized in a variety of application in computer networks and transportation systems to decrease the congestion and increase the usage of channels.


Congestion, Traffic distribution, Routing, Performance index. Control

Leave a comment

Your email address will not be published. Required fields are marked *