Optimisation de la distribution de données dans un système de systèmes collaboratifs

Un système de systèmes est un système dont les composants sont eux-mêmes des systèmes indépendants, tous communiquant pour atteindre un objectif commun. Lorsque ces systèmes sont mobiles, il peut être difficile d'établir des connexions de bout-en-bout. L'architecture mise en place dans de telles situations est appelée réseau tolérants aux délais. Les données sont transmises d'un système à l'autre – selon les opportunités de communication, appelées contacts, qui apparaissent lorsque deux systèmes sont proches – et disséminées dans l'ensemble du réseau avec l'espoir que chaque message atteigne sa destination. Si une donnée est trop volumineuse, elle doit être découpée. Chaque fragment est alors transmis séparément.

 

Dans ces travaux, nous supposons que la séquence des contacts est connue. On s'intéresse donc à des applications où la mobilité des systèmes est prédictible (les réseaux de satellites ou les réseaux de transports publics par exemple). Nous cherchons à exploiter cette connaissance pour acheminer des informations, depuis leurs sources jusqu'à leurs destinataires, le plus efficacement possible. Nous devons répondre à la question : "Quels éléments de données doivent être transférés lors de chaque contact pour minimiser le temps de dissémination" ?

 

Je formaliserai tout d'abord ce problème, appelé problème de dissémination, et montrerai qu'il est NP-difficile au sens fort. Je proposerai ensuite des algorithmes non-polynomiaux pour le résoudre. Ces derniers reposent sur des règles de dominance, des procédures de prétraitement, la programmation linéaire en nombres entiers, et la programmation par contraintes. Je rapporterai des résultats expérimentaux montrant l'efficacité des algorithmes développés.

 

Pour terminer la présentation, j’introduirai brièvement mes travaux de postdoc sur le traitement de très grands graphes pour la génomique, et plus particulièrement pour le séquençage ADN de novo. Nous aborderons des problématiques très différentes sur les architectures HPC (High Performance Computing) et les algorithmes BSP (Bulk Synchronous Parallel).