We consider the problem of optimal routing in a multi-stage network of queues with constraints on queue lengths. We develop three algorithms for probabilistic routing for this problem using only the total end-to-end delays. These algorithms use the smoothed functional (SF) approach to optimize the routing probabilities. In our model all the queues are assumed to have constraints on the average queue length. We also propose a novel quasi-Newton based SF algorithm. Policies like Join Shortest Queue or Least Work Left work only for unconstrained routing. Besides assuming knowledge of the queue length at all the queues. If the only information available is the expected end-to-end delay as with our case such policies cannot be used. We also give simulation results showing the performance of the SF algorithms for this problem.
L. K. and Bhatnagar, S., “Smoothed Functional and Quasi-Newton Algorithms for Routing in Multi-stage Queueing Network with Constraints”, in Distributed Computing and Internet Technology: 7th International Conference, ICDCIT 2011, Bhubaneshwar, India, February 9-12, 2011. Proceedings, R. Natarajan and Ojo, A. Berlin, Heidelberg: Springer Berlin Heidelberg, 2011, pp. 175–186.