New Challenges in Scheduling Theory

September, 12-17 2010, Centre CNRS "La Villa Clythia", Frejus

Bounded Multi Port Model: Motivations, Feasability & Application to Broadcast

SpeakerLionel Eyraud-Dubois

Co-authorOlivier Beaumont, Shailesh Agrawal Kumar, and Hejer Rejeb

The bounded multi-port model is a model for communications in distributed computing platforms, in which each node may be involved in several simultaneous communications, provided bandwidth constraints are respected. In highly heterogeneous environment, this model allows to make better use of the available bandwidth of large server nodes. In this talk, we discuss its feasability by showing that simple optimal algorithms exist for basic problems, and we will show that their implementation require to use QoS mechanisms to enforce the prescribed bandwidth sharing. We also study steady-state application-level broadcast, with an additional degree constraint to ensure the realism of the obtained solution. For this particular problem, we provide a polynomial algorithm based on a minimal resource augmentation.