Publications

Since 2000, sorted by subjects.

  1. All Optical Networks
  2. Stochastic Bounds
  3. Stochastic Automata Networks and Numerical Analysis of Markov Chains
  4. Stochastic Model Checking
  5. Stochastic Process Algebra
  6. Product Form Queueing Networks
  7. Simulation
  8. Active Networks, Mobile Networks
  9. Misc.

1. All Optical Networks

"Packet Loss Analysis in Optical Packet-Switched Networks with Limited Deflection Routing"
Accepted for publication in Photonic Network Communications, to appear 2007
I. Szczesniak, T. Czachorski, J.M. Fourneau

"Deflection Routing on a Torus is Monotone"
Positive systems Theory and Application conference, 2006, Springer LNCIS
A. Busic, J.M. Fourneau, D. Nott

"Modeling Fiber Delay Loops in an All Optical Switch"
IEEE QEST 2006, USA
A. Busic, M. Benmammoun, J.M. Fourneau 

"Preliminary results of Packet loss Analytilis in Optical Packet-switched networks with limited Deflection Routing"
Workshop of Modelling and Performance Evaluation for Quality of Service in Next Generation Internet in IEEE SAINT2005, Trento, 31 janvier 2005, pp 296-299
I. Szczesniak, T. Czachorski, J.M. Fourneau

"Performance evaluation of short-cut Eulerian routing"
Poster session, 1st EuroNGI Conference on Next Generation Internet Networks -  Traffic Engineering, 2005 Roma,
D. Barth, P. Berthomé, J.M. Fourneau, S. Vial, C. Laforest

"Transport time distribution for optimal  deflection routing on an odd torus"
Europar 05, LNCS 3648 Springer,  pp 975-983, Portugal
J.M. Fourneau, T. Czachorski

"Convergence Routing under bursty traffic: instability and an AIMD controller"
Second International Workshop on Practical Applications of Stochastic Modelling, Newcastle, UK, Jul. 2005,
in Electr. Notes Theor. Comput. Sci. 151(3): 97-109 (2006)
D. Nott, J.M. Fourneau

"Routing and Qos in an all optical packet network"
IEEE WOBS 2005, Boston USA
D. Barth, D. Chiaroni,  J.M. Fourneau D. Nott

"Mixed Routing for Optical Burst Switching"
ISCIS 2004, Antalya, Turkey, Springer Verlag, LNCS 3280, pp 257--266
J.M. Fourneau, D. Nott

"Performance Evaluation of an optimal deflection routing algorithm on an Odd Torus"
Archiwum Informatyki Teoretycznej I Stosowanej, Tom 16, pp 255-277, 2004
T. Czachorski, J.M. Fourneau

"Minimum Deflection Routing"
Photonic and Switching 2003, Septembre 2003 Versailles
F. Quessette

"Performance of a Mixed Deflection and Convergence Routing Algorithm"
Proceedings of the second Polish-German Teletraffic Symposium,  Gdansk, 2002, pp 47--54
T. Czachorski, J.M. Fourneau, S. Nowak, F. Quessette

"A mixed defflection and Eulerien routing : design and performance"
Europar 2002,  Paderborn, Allemagne, LNCS 2400
D. Barth, P. Berthome, T. Czachorski, J.M. Fourneau, C. Laforest, S. Vial

"Packet Selection in a deflection routing algorithm"
ISCIS 2002,  Orlando, USA, CRC Press
A. Borrero, J.M. Fourneau, F. Quessette

"Performance comparisons of Eulerian routing and deflection routing in a 2D-mesh all optical network"
European Simulation Multiconference (ESM2001), Prague, Rep. Tcheque, 2001
D. Barth, P. Berthome, A. Borrero, J.M. Fourneau, C. Laforest, F. Quessette, S. Vial


2. Stochastic Bounds

"Analyzing Weighted Round Robin policies with a stochastic comparison approach"
to appear in Computers and Operations Research, 2007
Mouad Ben Mamoun, Jean-Michel Fourneau, Nihal Pekergin

"Generalized class C Markov chains and computation of closed-form bounding distributions"
Probability in the Engineering and Informational Science, volume 21, pages 235-260, 2007
Mouad Ben Mamoun, Ana Busic, Nihal Pekergin

"Loss rates bounds in IP buffers by Markov chain aggregations"
5th ACS/IEEE International Conference on Computer Systems and Applications, (Aiccsa'07)},  IEEE Computer Society, Amman, Mai 2007
Hind Castel, Lynda Mokdad, Nihal  Pekergin
 
"Worst case analysis of batch arrivals with the increasing convex ordering"
European Performance Engeeniring Workshop (EPEW 06), Springer LNCS 4054, pp 196-210
A. Busic, J.M. Fourneau, N. Pekergin

"Bounds based on lumpable matrices for partially ordered state space", 
Structured Markov Chains Tools Workshop in ValueTools 2006, Italie, ACM Press, 
A. Busic, J.M. Fourneau

"Conditional steady-state bounds for a subset of states in Markov chains", 
Workshop Structured Markov chains, SMCtools06  in ValueTools 2006, ACM Press, Pise, Italie, 2006
Tugrul Dayar, Nihal Pekergin, S. Younes

"Polynomials of a stochastic matrix and strong stochastic bounds"
Markov Anniversary Meeting, 2006, Ed by Boson Books, pp 211-228
T.Dayar, J.M. Fourneau, N. Pekergin, J.M. Vincent

"Increasing convex monotone Markov chains: theory, algorithms and applications"
Markov Anniversary Meeting, 2006, Ed by Boson Books, pp 189-210,
M. Benmammoun,  A. Busic, J.M. Fourneau, N. Pekergin

"Loss rates bounds for  IP switches  in MPLS networks"
4th ACS/IEEE International Conference on Computer Systems and Applications, (Aiccsa'06)},  IEEE Computer Society, Dubai, Mars 2006
Hind Castel, Lynda Mokdad, Nihal  Pekergin

"Stochastic ordering based Markov process aggregations : applications to tandem queues"
CSNDSP 2006, Communication Systems, Networks and Digital Signal Processing,  IEEE Computer Society, 19-21 July 2006, Patras, Greece
Hind Castel, Lynda Mokdad, Nihal Pekergin

"A Matrix Pattern Compliant Strong Stochastic Bound"
Workshop of Modelling and Performance Evaluation for Quality of Service in Next Generation Internet in IEEE SAINT2005, Trento, 31 janvier 2005, pp 256-259
A. Busic, J.M. Fourneau

"Componentwise bounds for nearly completly decomposable Markov chains using stochastic comparison and reordering"
European Journal of Operational Research, 165 (2005), pages 810-825, 2005
Nihal Pekergin, Tugrul Dayar, Denizhan Alpaslan

"Bounds for Point and Steady-State Availability: An Algorithmic Approach Based on Lumpability and Stochastic Ordering"
European Performance Engeeniring Workshop (EPEW 05), LNCS 3670, Versailles, 2005
A. Busic, J.M. Fourneau, pp 94-108

"Bounding transient and Steady state dependability measures through algorithmic stochastic comparison"
Poster session, Performance 2005, France
A. Busic, J.M. Fourneau

"Stochastic Bounds on Partial Ordering: Application to Memory Overflows Due to Bursty Arrivals"
ISCIS 2005, 20th International Symposium, Istanbul, Turkey, 2005, Lecture Notes in Computer Science 3733 Springer, pp 244-253
J.M. Fourneau, N. Pekergin, H. Castel-Taleb.

"A Brief Introduction to an algorithmic approach for strong stochastic bounds"
Proceedings of the First Workshop on New Trends in Modeling, Quantitative Methods and Measurements, Zakopane, June 2004, pp 57--74
J.M. Fourneau, N. Pekergin

"A proof of st-comparison for polynomials of a stochastic matrix and how we can improve the accuracy of the st-bounds"
Proceedings of the Second International Working Conference on Performance Modelling and Evaluation of Heterogeneous Networks,  HET-NETÕs 2004 (Ilkley, July 2004)
T. Dayar, J.M. Fourneau, N. Pekergin, J.M. Vincent

"Algorithms for an irreducible and lumpable strong stochastic bound"
Linear Algebra and Applications, Vol 386, 2004, pp 167--186
J.M. Fourneau, M. Le Coz, F. Quessette

"An open tool to compute stochastic bounds on steady-state distributions and rewards''
IEEE Mascots 03, Orlando, USA, 2003,
J.M. Fourneau, M. Le Coz, N. Pekergin, F. Quessette.

"Transforming stochastic matrices for stochastic comparison with the st-order"
RAIRO-RO, V 37, 2003, pp 85-97
T. Dayar, J.M. Fourneau, N. Pekergin

"An algorithmic and numerical approach to bound the performance of high speed networks"
Mascots 2002,  Fort Worth, USA, IEEE, 
M. Benmammoun, J.M. Fourneau, N. Pekergin, A. Troubnikoff

"Closed-form stochastic bounds on the stationary distribution of Markov chains"
Probability in the Engineering and Informational Science, 16, pages 403-426, 2002
M. Ben Mamoun, N. Pekergin.

"Stochastic delay bounds of Fair Queueing policies through Weighted Round Robin policies"
Performance Evaluation, 47/2-3, pages 181-196, 2002
M. Ben Mamoun, N.Pekergin

"An algorithmic approach to stochastic bounds"
LNCS 2459, Performance evaluation of complex systems: Techniques and Tools, 2002, pp 64--88
J.M. Fourneau, N. Pekergin.

"Computing the bounds on the loss rates"
Yugoslav Journal of Operations Reserach, volume 12, pp 167-184, Décembre 2002
J.M. Fourneau, L. Mokdad, N. Pekergin. 

"Bornes stochastiques pour les taux de pertes dans un tampon  memoire ATM"
Calculateurs Paralleles, Reseaux et Systemes Repartis,  V13, N6, 2001, pp 533-555
O. Abuamsha, J.M. Fourneau, N. Pekergin.


3. Stochastic Automata Networks and Numerical Analysis of Markov Chains

"SANs and Lumpable Stochastic Bounds: Bounding Availability"
in Computer System, Network Performance and Quality of Service, Editeur Imperial College Press, 2006
J.M. Fourneau, B. Plateau, I. Sbeity, W.J. Stewart

"Class C Markov chains and transient analysis"
Positive Systems: Theory and Applications POSTA2006, pages 177-184, LNCIS 341, Control and Information Sciences, 2006
M. Ben Mamoun, N. Pekergin, S. Younes

"Tensor products and bounds for stochastic automata networks"
SIAM CSE 2005, Orlando
J.M. Fourneau, Brigitte Plateau, Ihab Sbeity, William Stewart

"Computing closed-form stochastic bounds on transient distributions of Markov chains"
Workshop of Modelling and Performance Evaluation of Quality of Service in Next Generation Internet in SAINT2005, Trento, pages260-264, IEEE Computer Society 2005
M. Ben Mamoun, N. Pekergin

"Lumpable continuous-time SANs"
European Journal on Operation Research, V148, N2, July 2003, pp 436-451
T. Dayar, O. Gusak, J.M. Fourneau

"Iterative disaggregation for a class of lumpable discrete-time SAN"
Performance Evaluation, Juin 2003
T. Dayar, O. Gusak, J.M. Fourneau

"Quasi-Birth-and-Death Processes with Level-Geometric Distribution"
SIMAX, Vol. 24, Number 1 pp. 281-291, 2002
T. Dayar, F. Quessette

"Stochastic Automata Networks and Near Complete Decomposability"
SIAM Journal on Matrix Analysis and Applications, 2001, Vol 23, pp 581-599
T. Dayar, O. Gusak, J.M. Fourneau

"Efficient analysis of discrete-time stochastic automata networks"
Seventh SIAM Conference on Applied Linear Algebra, 23-26 October 2000, Raleigh, North Carolina, USA
O. Gusak, T. Dayar, J.M. Fourneau

"Stochastic automata networks and NCD"
Workshop on Stochastic Networks, 26-30 June 2000, Madison, Wisconsin, USA
O. Gusak, T. Dayar, J.M. Fourneau


4. Stochastic Model Checking

"Model Checking of continous-time Markov chains by closed-form bounding distributions"
Quantitative Evaluation Sytems QEST2006, Riverside}, pages 199-211, IEEE Computer Society 2006
M. Ben Mamoun, N. Pekergin, S. Younes

"Stochastic Model Checking with Stochastic Comparison"
2nd European Performance Engineering Workshop 2005, EPEW05, pages 109-124, LNCS 3670, Formal Techniques for Computer Systems and Business Processes 2005
N. Pekergin, S. Younes

"Improving Stochastic Model Checking with Stochastic Bounds"
Workshop of Modelling and Performance Evaluation for Quality of Service in Next Generation Internet in IEEE SAINT2005, Trento, 31 janvier 2005, pp 264-267
J.M. Fourneau, S. Younes, N. Pekergin


5. Stochastic Process Algebra

"A Function-Equivalent Components Based Simplification Technique for PEPA Models"
LNCS Vol. 4054, pp:16-30, Ed. Springer Verlag. Proceedings of The Third European Performance Engineering Workshop (EPEW'06), Budapest, 21-22 June, 2006
J. Hillston, L. Kloul

"A precedence PEPA Model for Performance and reliability analysis"
European Performance Engeeniring Workshop (EPEW 06), Springer LNCS 4054, pp 1-15
J.M. Fourneau, L. Kloul

"Modelling Mobility with UML2.0 and PEPA nets"
Proceedings of The Sixth International Conference on Application of Concurrency to System Design (ACSD'06), Turku, 28-30 June, IEEE Computer Society pp:153-162, 2006
L. Kloul, J. Kuster-Filipe

"From Interaction Overview Diagrams to PEPA nets"
In Proceedings of the 4th Workshop on Process Algebras and Timed Activities (PASTA'05), Edinburgh 2005
L. Kloul, J. Kuster-Filipe

"A Unified Tool for Performance Modelling and Prediction, Reliability Engineering and System Safety"
Elsevier Science, vol.89, n.1, pp:17-32, July 2005
S. Gilmore, L. Kloul

"A Kronecker representation for PEPA nets models"
In Proceedings of the 3rd Workshop on Process Algebras and Timed Activities (PASTA'04), Edinburgh 2004
J. Hillston, L. Kloul

"PEPA Nets"
Performance Tools and Applications to Networked Systems: Revised Tutorial Lectures, Editors: M.C. Calzarossa & E. Gelenbe, LNCS Vol.2965, pp 311-335, 2004
S. Gilmore, J. Hillston, L. Kloul

"Modelling role-playing games using PEPA nets"
LNCS Vol. 3280, pp:523-532, Ed. Springer Verlag, Proceedings of The 19th International Symposium on Computer and Information Sciences (ISCIS'04), Kemer-Antalya, 27-29 October, 2004
S. Gilmore, L. Kloul, D. Piazza

"PEPA nets in practice: modelling a decentralised peer-to-peer emergency medical application"
LNCS Vol. 3236, pp:262-277. Proceedings of the 1st European Performance Evaluation Workshop (EPEW'04), Toledo, 30 September - 2 October, 2004
S. Gilmore, J. Hillston, V. Heanel, L. Kloul

"Software performance modelling using PEPA nets"
Proceedings of the 4th ACM SIGSOFT International Workshop on Software and Performance (WOSP'04), Redwood City, California, 14-16 January 2004
S. Gilmore, J. Hillston, L. Kloul,M. Ribaudo

"PEPA nets: a structured performance modelling formalism"
Performance Evaluation, Elsevier Science, Vol.54, pp:79-104, 2003
S. Gilmore, J. Hillston, L. Kloul, M. Ribaudo

"A Unified Tool for Performance Modelling and Prediction"
LNCS, N.2788, pp:179-192, Ed. Springer Verlag, Proceedings of the 22nd International Conference on Computer Safety, Reliability and Security (SAFECOMP'03), Edinburgh 23-26 September 2003
S. Gilmore, L. Kloul

"Performance Modelling with PEPA nets and PRISM"
In Proceedings of the 2nd Workshop on Process Algebras and Timed Activities (PASTA'03), Edinburgh, June 2003
S. Gilmore, J. Hillston, L. Kloul, M. Ribaudo

"From SAN to PEPA: A Technology Transfer"
In Proceedings of the 1st Workshop on Process Algebras and Timed Activities (PASTA'02), Edinburgh, June 2002
J. Hillston, L. Kloul

"Performance Modelling of Hierarchical Networks using PEPA"
Performance Evaluation, Elsevier, V50, 2002, pp 83-99
L. Kloul, J.M. Fourneau, F. Valois

"Performance Investigation of an On-Line Auction System"
Concurrency and Computation: Practice and Experience, Special Issue on High Performance Agent Systems, Scalability and Performance Management, John Wiley & Sons, N.13, pp:23-41, 2001
J. Hillston, L. Kloul

"An Efficient Kronecker Representation for PEPA Models"
LNCS, N.2165, pp:120-135, Ed. Springer Verlag, Proceedings of the Joint International Workshop, PAPM-PROBMIV 2001, Aachen, Germany, September 2001
J. Hillston, L. Kloul


6. Product Form Queueing Networks

"Computing the steady-state distribution of G-networks with synchronized partial flushing"
ISCIS 2006, LNCS 4263, Springer Verlag, Istanbul
J.M. Fourneau, F. Quessette

"Flow Equivalence and Stochastic Equivalence in G-Networks"
Computational Management Science, V1, N2, pp 179--192, 2004
E. Gelenbe, J.M. Fourneau

"G-Networks with Resets"
Performance Evaluation, 2002, V49, pp 179--191
E. Gelenbe, J.M. Fourneau

"Multiple Class Generalized Networks with iterated deletions"
Performance Evaluation, Elsevier, V42, pp 1-20, 2000
J.M. Fourneau, L. Kloul, F. Quessette

"Multiple Class G-Networks with list oriented deletions"
European Journal on Operation Research, V 126, pp 250-272, 2000
J.M. Fourneau, L. Kloul, D. Verchère

"G-reseaux dans un environnement aleatoire"
RAIRO-RO, V 34, pp 427-448, 2000
J.M. Fourneau, D. Verchère


7. Simulation

"Multicast tree allocation algorithms for distributed interactive simulation"
International Journal of High Performance Computing and Networking, Volume 4, Number 3-4, pp. 137 - 151, 2006
D. Barth, J. Cohen, C. Durbach

"Internet Topology Generation for Large Scale BGP Simulation"
3rd International Workshop on Internet Performance, Simulation, Monitoring and Measurement (IPS-MoMe 2005), Poland, 2005
J.M. Fourneau, H. Yahiaoui

"Génération de topologies réalistes pour la simulation du routage interdomaine"
Algotel 2005
J.M. Fourneau, H. Yahiaoui

"Simulation-based performance evaluation of routing in all-optical networks"
(en polonais), Studia Informatica, 2001, V22, N1
T. Czachorski, S. Nowak, J.M. Fourneau


8. Active Networks, Mobile Networks

"A secure code deployment scheme for active networks"
Proceedings of the 7th International Working Conference on Active Networks (IWAN'05), Sophia Antipolis, 21-23 November 2005
L. Kloul, A. Mokhtari

"Investigating Unfairness Scenarios in MANET Using 802.11b"
2nd ACM Workshop on Performance Evaluation of Wireless Ad Hoc Sensor, and Ubiquitous Networks (PE-WASUN 2005), Montreal, Canada, October, 2005
L. Kloul, F. Valois

"Algèbre des processus pour l'analyse des performances des noeuds actifs"
Techniques et Sciences Informatiques, Hermes Science, vol.24, n.2-3, pp:279-310, 2005
L. Kloul, A. Mokhtari

"Towards a feasible active networking scenario"
in Telecommunication Systems Journal, 27:2-4, pp:413-438, Kluwer Academic Publishers, 2004
J. Hillston, L. Kloul, A. Mokhtari

"Towards a Feasible Active Networking Scenario"
Proceedings of the 3rd IEEE International Conference on Networking (ICN'04), Guadeloupe, March 1-4 2004
J. Hillston, L. Kloul, A. Mokhtari

"Active Nodes Performance Analysis using PEPA"
Proceedings of the 19th United Kingdom Performance Evaluation Workshop (UKPEW'03), Warwick 9-10 July 2003
J. Hillston, L. Kloul, A. Mokhtari

"Modeling and Analysis of UMTS Hierarchical Network"
MASCOTS'2000, 8th International Symposium on Modeling, Analysis and Simulation of Computer and Telecommunication Systems, San-Francisco, Aout-Septembre 2000
F. Quessette, A. Troubnikoff, F. Valois

"Transient Analysis in Cellular Networks"
QNETs 2000, 4th Workshop on Queueing Networks with Finite Capacity, Ilkley, UK, 2000
T. Czachorski, S. Jedrush, J.M. Fourneau, F. Pekergin

"Cellular Networks : Transient State Models"
Proceedings of the First Polish-German Teletraffic Symposium, Dresde, RFA, 2000
T. Czachorski, J.M. Fourneau, S. Jedrush


9. Misc

"Choreographing Security and Performance Analysis for Web Services"
LNCS Vol. 3670, pp:200-214, Ed. Springer Verlag. Proceedings of The 2nd International Workshop on Web Services and Formal Methods (WS-FM'05), Versailles, France, 1-3 September, 2005
S. Gilmore, V. Haenel, L. Kloul, M. Maidl

"Lecture Notes in Computer Science 3670, Formal Techniques for Computer Systems and Business Processes"
Proceedings of the 2nd European Performance Engineering Workshop (EPEW 2005) and the 2nd International Workshop on Web Services and Formal Methods (WS-FM 2005), 1-3 September 2005, Versailles, France
M. Bravetti, L. Kloul, G. Zavattaro (Eds.)

"Analysing UML 2.0 activity diagrams in the software performance engineering process"
Proceedings of the 4th ACM SIGSOFT International Workshop on Software and Performance (WOSP'04), Redwood City, California, 14-16 January 2004
C. Canevet, S. Gilmore, J. Hillston, L. Kloul, P. Stevens

"Using Linear Regression to Characterize Data Coherency Traffic"
IEEE MASCOTS 2003, Octobre 2003, Orlando, FL
J.-T. Acquaviva, F. Quessette

"Dimensionnement des réseaux dans FADO : une première approche"
ROADEF 2005
D. Barth, T. Mautor, M. Ponchie, F. Quessette

 Imprimer  E-mail

Projet de Recherche

  1. Collaborations Nationales
  2. Collaborations Internationales
  3. Relations Industrielles
  4. Axes Transversaux du Laboratoire

 

1. Collaborations Nationales

     Participation à ResCom.

     Projets CNRS ou Ministère soutenus

1. Actions Télécommunications CNRS (1999-2000)

Le projet porte sur les outils et méthodes pour l'affectation efficace de ressources dans les réseaux mobiles et ATM.
Nous participons également depuis 2000 à une autre action Télécom CNRS qui porte sur la tarification (organisée par l'Université d'Evry, en collaboration avec l'équipe AlCAAp). Cette action se poursuit grâce à l'ARC Inria Prixnet.

2. Action Spécifique 182 (2003,2004)

Action sur la modélisation de réseaux informatiques, les outils et techniques d'évaluation de performances. Nous participons aux axes Outils et Méthodes de Bornes.

3. Projet RNRT ÊROMEO avec Alcatel

(voir axe Réseau Routage Performances)

4. ACI Sécurité Informatique (2003-2006) : Projet " SurePaths "

Ce projet (PRiSM, ID, IRISA) a pour but d'améliorer les méthodes d'évaluation de la fiabilité. Cette problématique de la fiabilité de systèmes redondants peut être vue  comme l'évaluation d'événements trop rares qui se produisent dans un espace trop grand. Nous développons plusieurs axes autour du calcul de bornes, de son intégration dans l'outil PEPS du laboratoire ID mais aussi autour de l'emploi des algorithmes de bornes stochastiques pour simplifier le calcul de formules sur des récompenses pour le " Stochastic model checking ".

5. ACI Sécurité Informatique (2004-2007): Projet "Sécurité du routage interdomaine dans Internet (SR2I)"

(voir l'axe Réseau Routage Performances)

6. ANR Projet Blanc (2005-2008) SMS (Simulation et Monotonie Stochastique).

Le projet a pour but d'explorer les différents concepts de monotonie stochastique en évaluation de performances. On s'interesse tout particulièrement à la simulation parfaite, à la simulation distribuée et aux solutions analytiques.

7. ANR Sécurité  Informatique (2006-2009) : Projet Checkbound avec Paris I, ID-LIG projet MESCAL, INT, LAMSADE

Projet sur le model checking stochastique à l'aide de technique de bornes et de simulation parfaite.

8. ANR Télécommunication EcoFrame (2006-2009) : Avec Alcatel

(voir axe Réseau Routage Performances)

2. Collaborations Internationales

1. Réseau Excellence Euro NGI (Next Generation Internet).

Depuis fin 2003, nous (et surtout Nihal Pekergin) sommes responsables pour le laboratoire de ce réseau d'excellence consacré à la conception du futur d'Internet. Nous avons rassemblé plusieurs équipes du laboratoire pour participer aux groupes de travail consacrées à la tarification, aux outils et méthodes d'évaluation de performances et bientôt aux réseaux mobiles. Cette action intègre des chercheurs du laboratoire provenant des équipes Alcaap, Epri et Réseau. Le réseau se poursuit jusqu'a 2008 sous le nom de Euro FGI.

2. Pologne (Silésie)

Nous avons une collaboration de longue date avec l'équipe du professeur T. Czachorski de l'Académie des Sciences de Pologne. Cette collaboration est actuellement soutenue par la DRI du CNRS sous la forme d'accords d'échanges (projet de 2 ans). Elle a été, au cours des années passées, soutenue par un réseau doctoral, par la DRI (plusieurs projets de 2 ans) et par une action intégrée MAE (2 ans, achevée en 2000).
La collaboration portait initialement sur l'utilisation des méthodes de diffusion pour modéliser des réseaux ATM. Cette méthode consiste à approximer un système discret (le nombre de clients) par un système continu et Gaussien dont l'équation d'évolution est plus facile à résoudre et qui possède les mêmes moyenne et variance. De plus cette méthode permet l'analyse du comportement stationnaire mais aussi des transitoires du processus. L'analyse transitoire permet par exemple de prendre en compte la dynamique des transferts intercellulaire dans un réseau sans fil. La problématique a été depuis élargie à la modélisation des réseaux mobiles et des réseaux tout optiques (simulation, analyse Markovienne ou approximations numériques)

3. Royaume Uni (Edimbourg)

C'est un projet avec l'équipe de Jane Hillston à l'Université d'Edimbourg soutenu à partir de 1999 et pour deux ans par la DRI du CNRS. La collaboration porte sur une extension des algèbres de processus (du type CSP) permettant d'introduire des temporisations stochastiques et sur son application au dimensionnement de réseaux (par exemple, les réseaux actifs, les jeux distribués et les serveurs d'enchères). L. Kloul a profité de son détachement au CNRS en 2002-2004 pour intensifier cette collaboration.

4. Turquie (Bilkent)

Le projet a été soutenu par la DRI-CNRS pour une période de deux ans à partir de 1999. La collaboration porte sur la résolution numérique de chaînes de Markov, les réseaux d'automates stochastiques et les comparaisons stochastiques. 

 

3. Relations Industrielles

 
Dans le domaine des réseaux, elles s'effectuent avec Alcatel et sont développées dans l'axe transversal Réseaux, Routage Performance. 

4. Axes Transversaux du Laboratoire

  • Axe transerval SEPIA (ALCAAP, ARPA, EPRI)
  • Axe transerval RRP (ALCAAP, ASR, EPRI)
  • Séminaire AMAP

 Imprimer  E-mail

Présentation Equipe EPRI

Évaluation des Performances des Réseaux Informatiques

  1. Présentation du Thème
  2. Thématique Scientifique
  3. Aperçu de l'État de l'Art

1. Présentation du Thème

Grâce à des méthodes analytiques ou numériques, des simulations séquentielles ou distribuées, ce thème étudie les performances des réseaux et la fiabilité des systèmes. Il a pour projet d'appliquer des méthodes classiques (simulation, chaînes de Markov ou files d'attente) mais aussi d'en développer de nouvelles afin de répondre à des problèmes nouveaux comme la qualité de service et le caractère fractal ou non stationnaire des trafics de données.

Le but est d'analyser des problèmes réels dans le domaine des réseaux haut débit, du routage, des réseaux mobiles et des architectures depuis les spécifications jusqu'à l'obtention de résultats numériques. Ces travaux font ainsi souvent l'objet de collaborations à l'intérieur du laboratoire (projets transversaux RRP et SEPIA), au niveau national (via des projets ANR ou plus anciennement ACI, AS et RNRT) et international (réseau d'excellence EnRO-NGI). Ce thème est composé d'une seule équipe.

2. Thématique Scientifique

Dans les systèmes informatiques ou de télécommunications actuels, interagissent, de façon complexe, un grand nombre d'éléments (paquets dans un réseau, mobiles dans un réseau sans fil, instructions élémentaires, etc.). Les services requis par ces objets services (déterministes, aléatoires ou contenant des synchronisations avec d'autres d'objets), leurs dates d'apparition (non indépendantes, plus ou moins sporadiques) rendent souvent leurs performances décevantes. Leur complexité les rend difficile à modéliser et à analyser, et encore plus à optimiser ou à prouver. Il est généralement impossible de considérer l'espace d'états car il est trop grand et les modèles n'ont pas en général de bonnes propriétés stochastiques permettant de les analyser simplement. De plus, l'ordre de grandeur très faible des quantités à obtenir et les différentes échelles de temps des composants rendent les approximations difficiles et les simulations peu efficaces car peu précises. 
Notre équipe a donc pour projet de développer de nouvelles méthodes d'évaluation de performances ou de la fiabilité, et ceci depuis les spécifications jusqu'à l'obtention de résultats numériques pour des problèmes réels. Nous nous intéressons donc aussi bien aux méthodes, qu'aux algorithmes et à leurs applications concrètes dans le domaine des réseaux, du routage, des mobiles et des architectures. Ce travail fait aussi l'objet de plusieurs collaborations tant à l'intérieur qu'à l'extérieur du laboratoire.

Les propriétés "difficiles" exhibées par des processus mesurés peuvent être traitées en ajoutant des dimensions à l'espace des états (par exemple en utilisant des processus modulés par des chaînes de Markov).
Malheureusement ceci augmente le nombre d'états du système, ce qui rend plus difficile aussi bien les modèles mathématiques que les simulations.

Pour les aspects analytiques et numériques, nos axes de recherche privilégient donc les méthodes qui permettent de structurer l'espace d'états de manière à s'affranchir de la taille du problème, ou, du moins, d'en limiter les conséquences depuis la modélisation jusqu'à la résolution effective.

Dans le domaine de la modélisation, nous avons participé au développement de deux méthodes de spécifications permettant une description modulaire et une représentation tensorielle efficace (les Réseaux d'Automates Stochastiques avec B. Plateau et PEPA-NET avec J. Hillston). Ces méthodes s'appuient sur des formalismes manipulés classiquement pour la preuve de programme (automate, algebre de processus) de manière à fournir un environnement permettant de prouver des propriétés qualitatives et quantitatives. On cherche aussi à obtenir des indicateurs de performance à partir d'une spécification UML. 

Pour les résolutions, nous nous intéressons principalement aux méthodes de bornes stochastiques en les associant tant aux méthodes analytiques (forme produit) qu'aux méthodes numériques. L'approche par comparaison stochastique consiste à construire des modèles qui fournissent des bornes supérieures ou inférieures des distributions stationnaires ou transitoires ou des premiers moments de ces distributions. Ces bornes sont en général obtenues par des modifications de trajectoires. Les modèles d'encadrement doivent être résolus plus facilement que le modèle initial : il doit donc être plus régulier pour permettre une solution analytique ou plus petit pour utiliser des algorithmes numériques. Il est donc complémentaire d'effectuer des recherches dans tous ces domaines. Nous appliquons ces méthodes à des problèmes difficiles de dimensionnement de réseau ou de fiabilité lorsque les méthodes de simulation usuelles ne sont plus efficaces.

En ce qui concerne la simulation, nos activités de recherche portent sur la distribution et le parallélisme mais aussi sur des travaux plus théoriques sur les calculs initiés lors de faute temporelle dans des simulations distribuées optimistes ou, plus récemment, sur la simulation parfaite par couplage dans le passé. Dans tous les cas, il s'agit d'utiliser le parallélisme soit pour améliorer la vitesse de construction d'un estimateur (simulation parallèle ou distribuée, couplage dans le passé) soit pour intégrer divers opérateurs dans la boucle de simulation (par exemple pour un entraînement). Les questions portent donc sur les problèmes informatiques (placement de données, techniques de communication) et stochastiques (construction d'estimateurs optimistes, propriétés de monotonie de certains modèles) pour effectuer des simulations efficaces.

3. Aperçu de l'État de l'Art

Face à la complexité de ces analyses, la recherche en évaluation de performances n'a pas actuellement privilégié de directions particulières. La théorie de files d'attente cherche à intégrer de nouveaux résultats à forme produit en temps discret ou avec de multiples transitions. La disponibilité d'ordinateurs rapides et éventuellement parallèles a également eu pour effet de relancer la recherche sur les résolutions numériques de grandes chaînes de Markov.
La recherche sur les systèmes en temps discret a aussi été à l'origine de nombreux travaux sur le mélange des transitions déterministes et aléatoires dans les réseaux de Petri. Tout ceci constitue ce qu'on pourrait appeler des modèles microscopiques où l'on cherche à prendre en compte toutes les transitions des systèmes étudiées.

A l'inverse, les approches macroscopiques vont s'intéresser aux flux plutôt qu'aux individus. Les approches fluides (dont fait partie l'approche de diffusion citée par la suite) remplacent les individus discrets par une grandeur continue généralement plus simple à évaluer, quitte à opérer des modifications à posteriori pour rendre un sens physique (discret) aux quantités obtenues. L'approche de type "Grandes Déviations" relève du même principe macroscopique mais sur l'axe des temps. On montre, par exemple, que la queue de distribution du nombre de clients dans une file est géométrique, ce qui permet d'évaluer la probabilité qu'elle dépasse un seuil et donc de dimensionner un tampon.

Ces deux approches peuvent être associées à un principe de construction de bornes au sens stochastique. Plutôt que de faire des simplifications non contrôlées, ces approches de bornes permettent, par la construction de divers schémas associés aux types de quantités à calculer, de fournir des modèles plus simples. Nous ne disposons pas encore d'une véritable méthodologie sur le sujet, essentiellement car il existe de nombreuses possibilités d'ordre et que la qualité des résultats est parfois médiocre. Mais de nombreuses équipes en France et à l'étranger travaillent maintenant sur le sujet. 

Enfin la recherche en simulation a pour but d'augmenter la taille des modèles analysables et la vitesse de calcul des estimateurs. Deux possibilités sont explorées : l'augmentation de la vitesse d'échantillonnage grâce au parallélisme et le guidage statistique pour obtenir des résultats plus rapides sur les événements rares.

 Imprimer  E-mail

Membres

Responsable 

Chercheurs Permanents 

Doctorants en cours

Anciens Doctorants

  • Mouad Benmamoun, Maître de Conférences (Université de Rabat, Maroc)
  • Armando Borrero, Professeur (Université des Andes Vénézuéla)
  • Corentin Durbachn, Ingénieur 
  • Mathieu Le Coz, Ingénieur
  • Amdjed Mokthari, Post Doc (France Telecom)
  • Alexis Troubnikoff, Ingénieur  
  • Fabrice Valois, Maître de Conférences (INSA de Lyon)

Anciens Chercheurs

  • Marisela Hernández, Maître de Conférences (Université d'Amiens)
  • Joanna Tomasik, Maître de Conférences (SUPELEC)

 Imprimer  E-mail

Axe Transversal : SEPIA

SEPIA : Systemes Embarqués, Performances, Intégration, Algorithmes

 

Equipes impliquées : ALCAAPARPAEPRI

Membres permanents : D. Barth, D. Barthou, W. Jalby, N.Pekergin, F. Quessette,  C. Timsit, S. Zertal

Doctorants : B. Cohen, E. Oseret

Post Doctorants : J.T. Acquaviva

Le projet regroupe des chercheurs de trois équipes : ALCAAP, ARPA et EPRI afin d'étudier l'architecture et l'algorithmique des systèmes embarqués ainsi que leurs performances. Cet axe est complémentaire de l'axe RRP (architecture des routeurs pour exécuter l'algorithmique de routage et de contrôle) mais possède aussi ses problématiques propres liées aux architectures embarquées sur satellite (ACI Masses de données Algol) et à l'utilisation de méthodes statistiques pour mieux comprendre les performances des architectures.

1. Analyse statistique des trafics dans les architectures DSM

Les architectures DSM (Distributed Shared Memory) offrent un compromis intéressant entre la puissance de calcul et la facilité d'utilisation. La particularité de ces systèmes, par rapport aux architectures à mémoire distribuée plus traditionnelle est de permettre de considérer toute la mémoire physique distribuée comme une mémoire virtuelle partagée. Cette mémoire virtuelle partagée est implémentée grâce à des protocoles complexes de cohérence où tous les processeurs doit envoyer des messages sur le réseau pour avertir les autres processeurs du devenir d'une ligne de cache de données. Lors de l'exécution de codes scientifiques, il apparaît que le trafic de cohérence est fortement structuré. Clairement cela provient de l'utilisation intensive dans ces codes de matrices et de vecteurs.

Acquaviva et Quessette ont proposé un algorithme pour caractériser dynamiquement le trafic de cohérence dans une architecture DSM. Cet algorithme repose sur des régressions linéaires, il résiste aux bruits, et permet de produire une caractérisation fine et quantitative du trafic reposant sur des critères statistiques, ce qui est peu courant en architecture et permet de nouvelles techniques de parallélisation ou de placement.

2. Architecture de routeurs

Il s'agit de proposer des architectures pour le plan de contrôle des routeurs de coeur ou d'accès capables de répondre aux contraintes de vitesse des paquets optiques. Diverses technologies sont examinées (FGPA, processeur programmable, Asic). Clairement seul le recours au parallélisme et la conception d'algorithme ou d'heuristiques incrémentales permettra de respecter les contraintes. Un des premiers exemples étudiés est le choix des paquets dans un routage modélisé par un graphe biparti pondéré. Le routage optimal s'effectue après recherche d'un couplage de poids maximal. Même si un algorithme optimal existe, il est impossible de l'implanter sur une architecture matérielle avec les débits demandés. On propose donc une heuristique rapide fournissant un premier choix non optimal qui peut être amélioré par des échanges tant que l'on a du temps.

3. Algorithmique et architecture pour satellite et astronomie

L'objectif de cette partie du projet est de développer, à travers une application concrète, un pôle de compétences groupant informaticiens des équipes ARPA, ALCAPP et EPRI et astronomes du GEPI pour la conception d'algorithmes et d'architectures embarquées pour le traitement de données à bord de satellites d'observation spatiale lointains.  L'application est la conception et le développement, à l'horizon 2010, du satellite GAIA devant apporter la vision tridimensionnelle et temporelle de notre Galaxie. Un projet de l'ampleur de GAIA est une chance pour l'objectif du projet car il est nécessaire pour nous de pouvoir contribuer à un projet scientifique concret pour nous positionner à terme comme pôle de compétences fort. Dans la conception de tels satellites, les progrès des technologies d'observation (par exemple la taille et le nombre des CCD) permettent aux satellites de recueillir une quantité de données en croissance continue mais des verrous technologiques demeuresnt :

  • la capacité de transmission au sol et les courtes périodes de visibilité de ces satellites lointains ne permettent pas de transférer en temps réel toutes les données recueillies (du Gigabit/seconde au Mégabit/seconde);
  • la capacité de mémorisation embarquée à bord des satellites ne permet pas un stockage important des données pour des raisons liées au poids, à l'énergie disponible et à la fiabilité des technologies dans un environnement spatial.
  • le fonctionnement des satellites doit être autonome,les données acquises contribuant au maintien de l'attitude du satellite.

Pour lever ce verrou technologique, il convient donc de traiter à bord et en temps courts les données recueillies par le satellite de façon à ne transmettre que des données pertinentes et/ou des résultats d'inférences sur ces données brutes. Dans le cas de GAIA, le satellite procède à une acquisition en continu pendant 5 ans avec une phase courte de transmission (8 heures) chaque jour. Le système visé doit donc d'une part effectuer la détection des objets en temps réel, identifier et sélectionner les données pertinentes à transmettre et enfin appliquer une compression sans perte.  Le projet se décompose en 3 activités :

3.1 Conception des algorithmes

Dans ce type d'applications, les critères de qualité d'un algorithme et de son intégration architecturale ne sont pas simplement mesurés en termes de temps mais aussi en termes d'énergie et de poids, ce qui introduit de nouvelles conceptions de complexité et de mesure de performances.  Dans le cas de GAIA, les algorithmes visent la sélection et la détection des objets stellaires pertinents, puis la compression des données acquises après traitement.  Il est clair qu'il faut penser l'algorithmique globale sans dissocier ces différents aspects, en oubliant pas qu'il s'agit qu'il s'agit d'algorithmes parallèles. Le traitement peut être vu en quatre points consécutifs :

  • Détection des objets pertinents.
  • Elimination des fausses observations.
  • Sélection et analyse des données détectées.
  • Compression à bord des résultats avant transmission.

Les données acquises forment une image constituée principalement d'amas de points lumineux sur un fond de faible luminosité.  Le satellite permet d'obtenir plusieurs images de la même partie de l'espace avec un léger décalage temporel et donc un déplacement uniforme des données entre ces images. Il s'agit donc ici d'un problème d'alignement d'images dans lesquelles certains objets disparaissent et d'autres se déplacent indépendamment du mouvement du satellite.

L'utilisation de méthodes classiques d'analyse d'images se heurte a priori à deux inconvénients.  Tout d'abord, elles font souvent appel à des capacités de traitement incompatibles avec l'architecture embarquée à bord du satellite.  Deuxièmement, les images à traiter peuvent plutôt être considérées comme des représentations graphiques d'éléments discrets.  Cette vision pourrait expliquer pourquoi ces méthodes paraissent avoir une efficacité limitée pour résoudre des problèmes similaires comme celui de l'alignement de gels de protéines soumis aux variations expérimentales (nous travaillons aussi sur ce sujet avec l'Inra de Jouy-en-Josas).  L'approche envisagée est plus centrée sur des méthodes de mathématiques discrètes comme la recherche de couplages maximaux.

La phase de sélection consiste à identifier l'amas de pixels correspondant à un (unique) objet détecté, par exemple en l'isolant dans un rectangle de pixels. Ce traitement peut encore utiliser des méthodes de convolution ou des algorithmes de mathématiques discrètes.  Une des difficultés est notamment de pouvoir dissocier plusieurs objets dont les amas de pixels se superposent.  Le but de la mission du satellite est en particulier de calculer la position de toutes les étoiles observées.  Les informations associées à chaque objet sélectionné doivent donc être pensées en ce sens.  Il s'agit également d'en calculer le centre (avec une précision bien inférieure au pixel) et la magnitude.  L'objectif est ensuite de ne conserver qu'une quantité minimum de données. Il parait judicieux d'étudier des stratégies alliant plus profondément sélection et compression.  Quel niveau de précision nécessaire dans les données émises (nombre de bits significatifs par exemple)?  Tous les objets ont-ils besoin d'un même degré de précision?  Peut-on déjà inférer partiellement les données brutes obtenues et ne transmettre que les différences par rapport à des résultats calculés?  La prise en compte du mouvement continu et prédictible du satellite ne pourrait-il pas mieux intervenir dans la compression de données d'images consécutives ?

3.2 Conception d'architectures

La problématique de conception du matériel de traitement de l'information embarqué à bord d'un satellite est tout à fait spécifique. Les systèmes sont destinés à effectuer des missions de longue durée, pendant lesquelles aucune maintenance humaine n'est possible.

La conception de ces systèmes doit pleinement intégrer tout ce qui touche à la redondance d'une part et ce qui concerne la validation du fonctionnement d'autre part. Les différentes technologies possibles au niveau du traitement sont de trois types : ASIC, FPGA et processeurs programmables. Il nous semble important d'utiliser à bon escient chacune de ces technologies. On peut en effet utiliser simultanément celles-ci en utilisant par exemple des Asic pour des prétraitements massifs d'information pour lesquels certains algorithmes sont bien connus et figés. Les Fpga peuvent alors être utilisés pour ajouter de la souplesse à ces prétraitements (opérateurs supplémentaires, paramétrages divers, dispositifs à interconnexions modifiables...). Les processeurs entièrement  programmables seraient alors dédiés aux traitements complexes nécessitant de «l'intelligence », une reconfiguration maximale et des possibilités d'écriture de code hautement optimisé.

La mise en oeuvre du parallélisme des algorithmes passe par un ordonnancement des calculs et des communications entre sous-systèmes. De nombreuses techniques d'ordonnancement ont été proposées dans la littérature, notamment pour des codes de calculs scientifiques ou de traitement du signal, cependant l'intégration des contraintes dues au temps réel et des contraintes de puissance électrique pose un challenge nouveau. Le choix des contraintes prises en compte à l'ordonnancement aura un impact sur le type d'ordonnancement (statique ou dynamique, affine ou non) et sur les méthodes de résolution (par programmation entière, par énumération partielle, par reconnaissance de cas déjà connus). La souplesse de l'architecture suggérée permet d'envisager la possibilité d'un ordonnancement hiérarchique, où les tâches de traitement ont un ordonnancement statique alors que les tâches de contrôle sont dynamiques. La génération du code pour ces processeurs avec des contraintes temps réel demande d'optimiser entre autres les accès à la mémoire (via une éventuelle hiérarchie), sources principales de consommation électrique et de délais d'attente du processeur. Cette optimisation peut également être basée sur des techniques d'ordonnancement (au niveau des instructions assembleur ou du code source) et guidée par une étude préalable des performances de l'architecture.

Enfin, on peut envisager et étudier la possibilité d'équiper l'architecture à bord du satellite de disques durs Raid. Un rapide calcul (3Mb/s de vitesse de transmission, 8h de transmission par jour) montre qu'il faut pouvoir stocker quelques dizaines de Giga-Octets de données. Donc, l'utilisation de disques de petite taille et de faible poids tels que ceux étudiés actuellement peut être une alternative intéressante. La question principale à traiter concerne donc la résistance de tels disques aux conditions physiques.

3.3 Simulation

La consommation d'énergie, le temps de calcul et la capacité de transmission vers le sol sont, comme on l'a déjà dit, trois contraintes fondamentales. Et le dimensionnement devra être effectué avant le lancement.D'autre part un satellite s'use avec le temps et sa production d'énergie a tendance à diminuer du fait de la dégradation de ses panneaux solaires.  Il serait alors intéressant de proposer un algorithme qui peut fonctionner avec différents modes dégradés qui serait alors moins performant mais moins coûteux en terme d'énergie.Nous proposons de simuler l'algorithmique embarquée afin de permettre non seulement d'effectuer ces dimensionnements, mais aussi de s'assurer que leur consommation et leur rapidité est acceptable au regard des paramètres nominaux. Cette activité de simulation peut également couvrir la gestion des défaillances dues aux perturbations et au vieillissement.

La complexité des algorithmes est classiquement calculée en modélisant leur exécution sur un paradigme de programmation qui est la machine de Turing, les contraintes de consommation n'étant généralement pas prises en compte.  La simulation permettra de mesurer à la fois la complexité temporelle et la complexité énergétique. L'activité de simulation nécessitera donc une phase de modélisation à la fois des données en entrée et de l'architecture.  Une fois cette modélisation effectuée, la simulation s'effectuera en logiciel afin de déterminer les choix les plus pertinents et devra s'effectuer en parallèle avec une simulation matérielle à base de {\sc Fpga}, afin par exemple de valider pragmatiquement le modèle.

Projets du Ministère et Partenaires industriels

  • Projet RNRT ROMEO (avec Alcatel, le LRI, le LAMI, l'INT, l'ENST Bretagne, CAPS-entreprise), (2003-2005)
  • ACI Masses de données, projet ALGOL (avec le LaMI (Evry) et le GEPI (Observatoire de Meudon), début en sept. 2004.

 Imprimer  E-mail

Plus d'articles...

Our website is protected by DMC Firewall!