Open Positions

Call for PhD applications - Prediction-based resource allocation for coflows

Until recently, resource allocation algorithms (routing, scheduling, etc.) were mainly designed in three different information settings: (I) the clairvoyant setting in which all the parameters (volumes, arrival instants,…) of the tasks are known in advance; (ii)  the non-clairvoyant setting where the parameters are unknown; (iii) and finally the stochastic setting where the algorithm is fed with the distribution of the parameters. 

The recent trend in data collection has made a fourth setting interesting. By running ML algorithms on the datasets containing parameters from previous instances, one can get an estimate (or predictions) of the parameters of the new tasks.  The principal research question that arises is how to design algorithms that take into account predictions. If the predictions were accurate, we could use the clairvoyant algorithms. On the other hand, if the predictions were completely useless, we could fall upon non-clairvoyant algorithms. However, when the predictions are known up to a certain degree of accuracy, it is not entirely clear whether existing algorithms can be applied off the shelf or new algorithms will be needed. 

This thesis will investigate prediction-based resource allocation for coflow scheduling in datacenter networks. A coflow is a collection of flows, each of which has to be finished before the coflow can be marked as done.  Scheduling of coflows with the objective of minimizing the average coflow completions times has been widely studied in the clairvoyant as well as non-clairvoyant setting, and approximation algorithms are known. 

Our contributions will be to design approximation algorithms for when predictions are given instead of the actual values.  We shall explore both the deterministic and the stochastic settings. The algorithms should be consistent, that is behave almost as well as the best clairvoyant algorithms when the predictions are accurate, and robust, that is maintain worst-case guarantee even with terrible predictions.

Host laboratory: the thesis will be carried out within the SARA team of LAAS-CNRS, Toulouse, France. It will be supervised by Olivier BRUN and Balakrishna PRABHU.

Starting date:  September 2024.

Application material: should include a CV, a motivation letter, marks for the last two years and the names of one or two persons who can write a recommendation letter for the candidate. 

Contacts (for sending the application material or for queries): Olivier BRUN (brun@laas.fr) et Balakrishna PRABHU (balakrishna.prabhu@laas.fr).