Les réseaux de télécommunication voient une augmentation constante des flux liés aux services en temps réel (voix sur IP, jeux vidéo, entraînement de grands réseaux de neurones...), lesquels nécessitent une garantie de délai de transmission. Le routage de tels services nécessite idéalement de contrôler le délai maximum associé à chaque chemin emprunté, qui peut être exprimé comme la somme des délais de chaque lien du chemin. Si le délai associé à un lien est considéré comme constant, l'optimisation d'un tel routage ne pose pas de difficultés algorithmiques. Cependant, le délai associé à un équipement télécom augmente fortement avec sa charge ; cette dépendance est bien modélisée par la fonction de Kleinrock d(y) = 1c−y oùy représente la charge de l'équipement et c la capacité de l'équipement. On remarque que, lorsque la capacité résiduelle c − y tend vers 0, le délai associé explose.

Dans ce travail, nous étudions le routage de services en temps réel, modélisé comme un flux multi-commodités soumis à des contraintes de délais. Les délais des chemins utilisés par les commodités dépendent, via une fonction de Kleinrock, de la charge de chacun des arcs traversés par ces chemins. L'objectif sera de maximiser la proportion de chaque commodité transportée ("concurrent multi-commodity flow").