Miklós MOLNÁR

  Maître de conférences English version

Adresse :
 
INSA
Département informatique
20, Av. des buttes de Coësmes
F-35043 Rennes Cedex, France
Tel : +33 (0) 2 23 23 86 79
Fax : +33 (0) 2 23 23 84 53		 Projet ARMOR
Campus de Beaulieu,
F-35042 Rennes Cedex, France
Tel : +33 (0) 2 99 84 74 42
Fax : +33 (0) 2 99 84 71 71

email :          molnar@irisa.fr


Domaines de recherche
 


 Mes activités de recherche

Problème de Steiner dans les réseaux
Du point de vue du support  optimal, la diffusion  multicast  dans un réseau  correspond à  un arbre couvrant minimal partiel (appelé également arbre minimal de Steiner). La construction d'un tel arbre étant NP-complete, plusieurs algorithmes heuristiques fournissant un arbre approché en utilisant un temps polynomial ont été formulés. Il est intéressant de trouver des bons compromis qui peuvent diminuer la longueur de l'arbre construit en utilisant un temps de calcul raisonnable (toujours polynomial.) Beaucoup d'heuristiques utilisent les chemins les plus courts pour relier les membres du groupe multicast. Le temps de calcul de ce genre de construction est toujours faible mais la longueur des arbres résultants n'est pas toujours acceptable. Nous sommes intéressés par des algorithmes de construction de l'arbre approché de l'optimum qui établissent les connexions  entre les sous-arbres déjà  existants de l'arbre couvrant partiel à l'aide des arbres minimaux de Steiner simples. Notre première proposition concerne la modification de l'heuristique  bien connue de Kruskal  ( 1  et  2 ). Cette même idée peut être appliquée sur  l'heuristique  de Takahashi et Matsuya ( 3  ).
Nos heuristiques soulèvent la question suivante : quand on améliore un arbre couvrant partiel à l'aide de l'ajout  d'un sous-arbre, quelle partie de l'arbre original peut être supprimer afin d'éliminer les boucles causées ?  Dans le cas général, la structure pouvant être éliminée est une forêt. Dans notre étude, nous donnons  des méthodes de  réduction du problème posé ainsi qu'une solution algorithmique pour trouver la forêt déductible de longueur maximale ( 4 ).
Actuellement, nous travaillons sur le problème des bornes du ratio d'approximation des heuristiques proposées.

Communication multicast avec QoS
Les applications utilisant des protocoles multicast peuvent être sensible à des différents critères de qualité (bande passante, délai, gigue,
probabilité des pertes, ...). La recherche des arbres couvrants partiels qui satisfont aux besoins est primordiale pour ces applications.
Étant donné que l'état du réseau change sans cesse, les métriques permettant l'optimisation sont souvent modélisées par des variables
aléatoires. La connaissance des valeurs est incomplète. Nous avons transformé le problème du routage multicast avec contrainte
de bande passante lorsque l'information est incomplète en un problème de Steiner déterministe. Nous avons utilisé la méthode "tabou"
pour s'assurer de la bonne qualité des solutions sous optimales en un temps polynomial ( 5 ). L'algorithme de recherche "tabou" est  proposé également  pour accélérer  la détermination de l'arbre optimal dans le cas du délai de bout en bout ( 6 ). Dans le cas où l'incertitude du délai se limite sur un intervalle relativement petit et la distribution du délai dans cet intervalle peut être supposée uniforme, une discrétisation du problème peut aider la construction de l'arbre quasi-optimal ( 13 ).

Communication multicast dans les réseaux optiques WDM
Dans les réseaux  optiques WDM, la gestion des communications  multicast possède des  particularités  intéressantes.  A côté du problème
de conversion de longueur d'onde, d'autres phénomènes limitent le choix du support de la  diffusion de multicast: certains routeurs ne
 peuvent pas dupliquer les messages. La construction des arbres couvrants partiels  doit tenir en compte les possibilités des noeuds.
L'application des algorithmes classiques de construction d'arbres couvrants partiels nécessite des modifications. L'adaptation de la construction des arbres de plus courts chemins nécessite une pré-traitement ( 12 ).
Pour éviter les sous-graphes dans lesquels la duplication des messages n'est pas possible, les algorithmes développés à l'Irisa qui utilisent les k-distances pour construire des arbres sont particulièrement intéressants ( 11 ).

Reroutage rapide
Actuellement, le temps de convergence du protocole OSPF est à une minute. Cette convergence lente ne peut pas être tolérée par des
applications temps réel quand  il s'agit d'une panne du réseau. Nous proposons des mécanismes complémentaires  pour OSPF permettant la réduction du temps de convergence en calculant un chemin de secours disjoint pour chaque destination. L'algorithme  TDSP  ("Two Disjoint Shortest Paths")  calcule deux chemins indépendants en un seul passage avec la complexité  O(n2) (cf. 7  and  8 ).

Activités antérieures

Optimisation des systèmes de gestion de stocks
Dans ma thèse, l'applicabilité de l'approximation stochastique aux problèmes de stocks  a été analysée quand le gestionnaire ne possède pas de connaissances a priori concernant les variables aléatoire de ses modéles.  Plusieurs stratégies de gestion sont présentées dans ( 9 ).

Réseaux de neurones
Les réseaux de neurones sont des excellents approximateurs généraux. Souvent, l'apprentissage des poids des connexions est basée sur la méthode  bien connue de  "retro-propagation de l'erreur".  Dans cette méthode, le gain de réactualisation des valeurs est choisi le plus souvent intuitivement. Une stratégie du choix optimal de ce gain peut être basée sur  le processus d'apprentissage afin de l'accélérer  ( 10 ).

Publications

Enseignement au Département Informatique de l'Insa