Advances in Operations Research
Volume 2011 (2011), Article ID 645954, 21 pages
http://dx.doi.org/10.1155/2011/645954
Research Article

Optimal Routing for Multiclass Networks

Hisao Kameda,1 Jie Li,1 and Eitan Altman2

1Graduate School of Systems and Information Engineering, University of Tsukuba, Tsukuba Science City, Ibaraki 305-8573, Japan
2INRIA, BP93, 06902 Sophia Antipolis Cedex, France

Received 30 September 2010; Revised 4 April 2011; Accepted 5 April 2011

Academic Editor: Yi Kuei Lin

Copyright © 2011 Hisao Kameda et al. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

Abstract

Overall optimal routing is considered along with individually optimal routing for networks with nodes interconnected in a generally configured manner and with multiple classes of users. The two problems are formulated, and we discuss the mutual equivalence between the problems, the existence and uniqueness of solutions, and the relation between the formulations with path and link flow patterns. We show that a link-traffic loop-free property holds within each class for both individually and overall optimal routing for a wide range of networks, and we show the condition that characterizes the category of networks for which the property holds.