Insensitive Load balancing and bandwidth allocation in Communications Networks

Along this quite general problematic, my research has first specifically focused on load balancing aspects in communication networks. How to route incoming requests to a set of web servers and how to derive the performance of optimal or nearly optimal routing is one example of motivation for this work. Though the literature on load balancing in queuing networks is huge, the number of practical results that can be stated as engineering rules or as performance evaluation benchmark is known to be rather small. Typically, intuitive dynamic load balancing scheme as joining the shortest queue is proved to be optimal only for a set of parallel symmetric servers and for specific traffic conditions (Poisson arrivals and exponential service times). Even for this rather constrained context, nearly no analytical performance results has been obtained. My work has build on the new approach of data networks performance evaluation developed this last decade, based on modeling communication networks by processor sharing queuing networks and leading to robust explicit results in the spirit of the crucial Erlang formula for telephone traffic.

The main idea is to consider classic optimal control problems, (known to be theoretically intractable, in general), and to restrict the set of admissible policies so that the problem becomes tractable. More specifically, I restricted the optimization to those strategies whose performance is insensitive in the sense that the stochastic process describing the network state (the number of customers in each queue) has a stationary measure which depends on the traffic characteristics through their first order statistic only. Depending on the criterion of performance (motivated by technological or engineering issues) I showed that this approach can lead either to powerful results or can be insufficient to evaluate the optimal policies.


Publications:

•Toward an Erlang formula for multiclass networks

Queueing Systems: Theory and Applications, 66(1), 53-78, 2010,

•Insensitive vs efficient load balancing in networks without blocking

Queueing Systems: Theory and Applications, 54(3), 193-202, 2006 [.pdf],

•Optimal insensitive routing and bandwidth sharing in simple data networks

with J. Virtamo,

Sigmetrics, 193-204, ACM Press. (Perf. Eval. Review) 2005 [publi_site] [.ps],

•Insensitive load balancing

with T. Bonald and A. Proutière

Sigmetrics/Performances 367-377, ACM press (Perf. Eval. Review) 2004 [publi_site] [.ps] ,

•Partage de charge et allocation de capacite insensibles dans les reseaux de telecommunication (in french) PHD Thesis, [.pdf].