Assistant
Professor 
Version
française
Address :
| 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 |
Project 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
Steiner Problem in Graphs and Related Works
From the topology point of view, the lower cost multicast diffusion
in a network corresponds to a partial minimum spanning tree (named
also minimal Steiner tree). The construction of such a tree being NP-complete,
several heuristic approximation algorithms with polynomial
time have been formulated. It is interesting to find good compromises
which can decrease the tree length by using a reasonable
computational time to build and manage the connection. Many of the
heuristics use the shortest paths to connect the multicast group
members. The computational time of this kind of construction is weak
but the length of the resulting trees is not always acceptable. In our
research, we give some scalable approximate construction algorithm
of the optimal tree that can diminish the length of the multicast tree
and still be in polynomial time. This construction makes connections
like simple minimum Steiner trees between the already existing
sub-trees of the partial spanning tree. Our first proposition is the
modification of the well known Kruskal's heuristic ( 1
and 2 ). The same
idea can be applied on the Takahashi-Matsuyama's heuristic ( 3
).
Our heuristics raise the following question: when we are improving
an existing partial spanning tree by addition of a (more advantageous)
partial subtree, which part of the original tree can be removed in
order to eliminate the introduced cycles? In the general case, the
structure
which can be removed from a tree after the addition of another one
(to find a spanning tree covering a given set of nodes) is a forest. We
give a reduction method of the arising problem as well as the algorithmic
solution to identify the maximum removal forest ( 4 ).
Recently we are working on the limite of the approximation ratio of
our propositions.
Multicast Communication with QoS
In certain cases analysis of multicast routing in packet switched communication
networks when there is no available exact link state
information in the network is needed. From this analysis we develop
novel algorithms for QoS routing. The multicast routing with
bandwidth and cost requirement in the case of incomplete information
is reduced to a deterministic Steiner tree problem. The simulation
results show the performance which can be achieved by implementing the
methods in QOSPF environment ( 5 ). A fast algorithm
is proposed for the end-to-end delay problem in ( 6 ).
Multicast Communication in All Optical WDM Networks
The multicast communication becomes a particular and interesting problem
in all optical WDM networks. Beyond the wavelength
conversion problem, an other phenomena constrains the multicast
diffusion: some switches can not split the messages. The partial
spanning tree construction can be out of consideration for the splitting
capability of nodes.
Fast Re-routing
Actually, OSPF convergence time is about 1 minute. However, this convergence
time is not low enough to be tolerated by real time
applications. We propose complementary mechanism to OSPF which reduces
the protocol convergence time by calculating in advance for
each possible destination in the network an alternate backup path which
is disjoint from the primary used path. The TDSP "Two Disjoint
Shortest Paths" algorithm that we had proposed calculates two disjoint
paths in one pass with a complexity of O(n2) (cf. 7
and 8 ).
Earlier activities
Optimization of Stochastic Inventory Systems
The application of stochastic approximation has been proposed in order
to work out the optimization of inventory control problems when
the inventory manager does not have a priori knowledge about the random
variables of the system. Multiple models was proposed in my thesis work(
9
).
Neural Networks
Neural networks are good general function approximators. Often
the learning of neural networks is realized with the help of well known
"back propagation" method. The acceleration of the learning process
with a second learning method is possible ( 10 ).
at the Department
of Electronic Engineering of Insa
at the Department
of Electronic and Communication Systems of Insa