Invitation à la soutenance de thèse de Nicolas Stefanovitch (vendredi 22 octobre 2010 à 10h, LIP6, salle 105)

Bonjour,

j'ai le plaisir de vous inviter à la soutenance de ma thèse intitulée :

"Contributions à la résolution de problèmes d'optimisation de
contraintes distribuées dynamiques à l'aide de modèles graphiques pour
la coordination multiagents"

ainsi qu'au pot qui suivra.

============
Date et lieu
============

La soutenance se déroulera ce vendredi (vendredi 22 octobre 2010) à
10h00 au LIP6, salle 105, barre 25-26 (1er étage). Accès au LIP6 :
http://www.lip6.fr/informations/comment.php

======
Résumé
======

Les systèmes informatiques sont de plus en plus autonomes et couplés.
Le contrôle de leur comportement nécessite le développement
d'algorithmes dédiés prenant en compte simultanément les problèmes de
décision auxquels ceux-ci ont à faire face ainsi que l'architecture
distribuée sous-jacente de ces systèmes. Ce domaine est celui de la
coordination de systèmes multiagents.

Les systèmes multiagents sont persistants, ouverts et doivent gérer
des problèmes évoluant dynamiquement tout en garantissant leur
comportement dans un contexte opérationnel incertain. En tant que
système artificiel, il est souhaitable qu'une procédure de
coordination garantisse l'optimalité des décisions. En tant que
système réel, il est souhaitable qu'une solution soit trouvée le plus
rapidement possible. En tant que programme informatique distribué, il
est souhaitable que la procédure de coordination soit capable de
s'adapter à la modification dynamique du système ainsi que d'exploiter
le parallélisme.

Nous abordons le problème de la coordination multiagents modélisé en
tant qu'un problème d'optimisation de contraintes distribué dynamique
(DynDCOP), et où nous utilisons les modèles graphiques comme
mécanismes de base pour résoudre ceux-ci. Notre démarche consiste à
étendre ces approches pour les adapter aux contraintes d'exécution des
systèmes multiagents.

Nous proposons trois contributions. La première est un algorithme
approché avec garanties qui permet de réaliser un compromis
paramétrable entre optimalité et décentralisation de la résolution. La
seconde contribution est un algorithme adaptant la création du modèle
graphique aux ressources du système multiagents (structure du réseau
de communication, bande passante des liens de communication et vitesse
de calcul des agents) et à l'ordonnancement des calculs sur celui-ci.
Enfin dans notre troisième contribution nous proposons un algorithme
de clusterisation partielle paramétrable permettant, pour un temps
maximal d'inférence donné, d'exploiter à la fois la réactivité des
modèles graphiques cycliques et la qualité des solutions des modèles
graphiques acycliques.

====
Jury
====

- Philippe Mathieu, Professeur, Université de Lille 1 (rapporteur)
- Yann Chevaleyre, Professeur, Université Paris Dauphine (rapporteur)
- Patrice Perny, Professeur, Université de Paris 6 (examinateur)
- René Mandiau, Professeur, Université de Valenciennes (examinateur)
- Amal El Fallah Seghrouchni, Professeur, Université de Paris 6
(directice de thèse)

Cordialement,

Nicolas Stefanovitch

[Invitation] Soutenance de thèse de Sondes Khemiri le lundi 25 Octobre à 10h

Bonjour,

J'ai le plaisir de vous inviter à ma soutenance de thèse intitulée
"Dimensionnement et allocation de ressources dans les réseaux
métropolitains IEEE 802.16" et au pot qui la suivra.

La soutenance se déroulera le lundi 25 Octobre 2010 à 10h, au
Laboratoire d'Informatique de Paris 6 (LIP6) situé au: Site Jussieu
rotonde 25-26/ au 4 place Jussieu 75005 Paris.
Plan d'accès : http://www.lip6.fr/informations/comment.php

Salle de soutenance: 25-26/101
Salle du Pot: 26-00/101

Jury:

Rapporteur: Fabrice Valois, Professeur, INSA Lyon
Rapporteur: Sami Tabbane, Professeur, SUP'COM Tunis
Examinateur: Mario Gerla, Professeur, UCLA Los Angeles
Examinateur: Jérome Brouet, Expert senior architecture réseaux, Alcatel
Examinateur: Sébastien Tixeuil, Professeur, Université Pierre et Marie Curie
Examinateur: Nadjib Achir, Maîıtre de conférences, Université Paris 13
Examinateur-invité: Tijani Chahed, Professeur, Télécom Paris Sud
Directeur: Guy Pujolle, Professeur, Université Pierre et Marie Curie
Co-encadrant: Khaled Boussetta, Maîıtre de conférences,
Université Paris 13

Résumé:
Les standards WiMAX ont décrit en détails les outils nécessaires pour
mettre en place un réseau de données à haut débit mais ont laissé le
libre choix aux équipementiers d'implémenter leur propre mécanismes de
gestion de la QoS.

Cette thèse s'intéresse à la thématique très motivante de la QoS dans
les réseaux WiMAX et plus particulièrement au dimensionnement des
mécanismes de gestion de la QoS. A savoir: le contrôle d'admission,
l'ordonnancement et l'allocation de ressources au niveau de la couche
Physique. Le challenge de ces mécanismes consistent à prendre en
considération les concepts introduits par les standards IEEE 802.16
aussi bien fixe que mobile comme la modulation adaptative, les
techniques de permutation des fréquences, la mobilité et les
techniques de multiplexage OFDMA et TDMA. Ceci en intégrant les
exigences des applications visées par la technologies WiMAX.

Pour ce faire, notre approche a consisté à identifier les mécanismes
de gestion de la QoS pertinents qui ont été présentés dans la
littérature, de les adapter aux nouveaux concepts de la technologie
WiMAX et de proposer des variantes de mécanismes de QoS. Ces derniers
ont été conçus dans une perspectives de performance de bout en bout,
tout en tenant compte des contraintes des applications et des
spécificités des couches physique et MAC des standards WiMAX.

Une importante contribution de la thèse réside dans la proposition de
modèles mathématiques permettant d'évaluer les performances du système
en considérant nos mécanismes de QoS et de déterminer grâce à
l'utilisation de méthodes heuristiques les meilleurs paramètres de
dimensionnement possibles.

Abstract:
This thesis addresses the issue of QoS in WiMAX networks and
esspecially the dimensioning of management bandwidth WiMAX network
mecanisms i.e: Call admission controll, scheduling mecanism and
ressource allocation in physical layer. The challenge of these
mechanisms are to take into account concepts introduced by the fixed
and mobile WiMAX network as well as adaptive modulation, the
subchannelization mecanism, mobility and OFDMA and TDMA multiplexing
techniques. This by considering application requirements supported by
WiMAX. To do this, our approach was to identify relevant QoS
management mechanisms presented in literature, and to adapt them to
new concepts of WiMAX technology and propose alternative QoS
mechanisms. We proposed an end to end QoS module by taking into
account applications constraints and the caracteriscs of physical and
MAC layers of the WiMAX standard. An important contribution of the
thesis lies in the proposed mathematical model to evaluate the
performance of our system by considering QoS mechanisms and to
determine through the use of heuristics the best possible
dimensionning parameters. The first contribution of this thesis
proposes a mathematical model with the aim to give guidelines for the
dimensioning of WiMAX bandwidth provisioning service to residential
customers in fixed WiMAX network, we considered in this work a
combined Guaranteed minimim and Upper Limits CAC strategy. The second
contribution is to determine, using an analytical model and a
heuristic approach, the nearly-optimal sizes of the partition sizes
dedicated to each type of connection in mobile WiMAX by considering
the Complete partionning CAC. Finally, we propose a wireless resource
allocation (mapping) mecanism of a Mobile WiMAX cell based on OFDMA
access technique.

Très cordialement,
Sondes Khemiri

Invitation à la soutenance de thèse de MTNGO (Mercredi 13 octobre 2010 à 10h, au LIP6, salle 211 tours 55-65)

Bonjour,

j'ai le plaisir de vous inviter à ma soutenance de thèse, intitulée

"Modélisation et Optimisation des plans de feux - Application
de la méthode de décomposition de Benders"

ainsi qu'au pot qui suivra.

La soutenance se déroulera le mercredi 13 octobre
à 10h en salle 211 tours 55-65, 2ème étage sur le campus de Jussieu.

------------------------
Composition du jury
------------------------
Membres du jury :
Perny Patrice, Professeur, Département DESIR, LIP6, (Président)
Lisser Abdel, Professeur, LRI, Université Paris-Sud 11,(Rapporteur)
Haj-Salem Habib, Directeur de recherche - HDR, INRETS/GRETIA, "Le
Descartes 2", (Rapporteur)
Lebacque Jean-Patrick, Ingénieur Général des Ponts et Chaussées,
INRETS/GRETIA, "Le Descartes 2", (Examinateur)
Minoux Michel, Professeur, Département DESIR, LIP6, (Directeur de thèse)
Nguyen Viet-Hung, M.C, Département DESIR, LIP6, 4 place Jussieu,
(Co-directeur de thèse)

Le plan d'accès est consultable à l'adresse suivante :
http://www.upmc.fr/FR/info/ Venir_UPMC/05

Cordialement,
Minh Tuan NGO

----------
Résumé
----------
L'objet principal de cette thèse, réalisée en collaboration avec la
Société PHOENIX-ISI, consiste à développer un modèle de contrôle optimisé
des feux de signalisation dans un réseau routier urbain. Il s'agit plus
précisément de déterminer les plans de feux, c'est à dire pour chaque
carrefour : durée du feu vert et décalage (offset) dans le cadre de
réseaux de type axial (un itinéraire) ou de type maillé (par exemple, un
quartier d'une agglomération). L'objectif (à minimiser) consiste à partir
des données de circulation du réseau (débit entrant, répartition
directionnelle des flux) et en utilisant un modèle de simulation de la
propagation des flots de véhicules, à rechercher un plan de feux
minimisant le retard total subi par les véhicules au cours de leur
traversée du réseau.

Le travail de recherche présenté ici se décompose en deux parties
principales. La première partie consiste à développer un modèle de
simulation de trafic permettant de représenter, de façon précise,
l'écoulement des différents flux de trafic dans le réseau étudié pour un
plan de feux quelconque fixé. La deuxième partie de la thèse est consacrée
à la résolution algorithmique du problème MIP (problème en nombres entiers
mixtes) élaboré dans la première partie. Nous proposons un algorithme basé
sur la méthode de décomposition de Bender. Essentiellement, un tel
algorithme doit résoudre un program linéaire de très grande taille à
chaque itération afin de générer d'une coupe de Benders. Nous montrons
que, pour notre problème MIP nous pouvons le faire de façon itérative (par
une procédure de simulation inversée) et donc plus rapidement en
exploitant une structure particulière de la matrice de contraintes. Nous
présentons enfin une série d'expériences numériques prouvant l'efficacité
de l'algorithme proposé.

Mots clés : Régulation du trafic urbain, contrôle des feux de
signalisation, simulation trafic routier, optimisation combinatoire,
programmation en nombres entiers mixtes, méthode de décomposition de
Benders.

The purpose of this thesis, conducted in collaboration with the
Phoenix-ISI company is to develop a model for the traffic light control
problem in urban network. The objective is to determine a signal timing
plan which minimizes the total delay to which vehicles are subjected
during their passage through the network.

The research presented here is divided into two main parts. The first part
is to develop a traffic flow model based on network traffic data (inflow,
flow directional distribution) to represent accurately the flow of
different traffic flows in the studied network. The second part consists
in solving a MIP (Mixed Integer Problem) issued from the simulation model
in the first part. We propose an algorithm based on the Bender's
decomposition method. Basically, such an algorithm should solve a huge
linear programming problem to generate Bender's cuts in each iteration. We
prove that, for our MIP we can do it much faster by an iterative method
("inverse simulation" procedure) which exploits a special structure of the
matrix of constraints. We present finally a series of numerical
experiments proving the efficiency of the proposed algorithm.

Keywords: urban traffic control, traffic signal control, Traffic
simulation, optimization, MIP problem, Benders decomposition method.

Invitation à la soutenance de thèse de Brice AUGUSTIN (Lundi 18 octobre 2010 à 11h, au LIP6, salle 105)

Bonjour,

C'est avec le plus grand plaisir que je vous invite à ma soutenance de
thèse intitulée :

"Traçage de Routes Internet en présence de Répartition de Charge /
Tracing Internet Routes under Load Balancing".

Ainsi qu'au pot qui suivra.

La soutenance se déroulera le :

Lundi 18 octobre 2010 à 11h00, au LIP6 salle 105 (barre 25-26)

http://www.upmc.fr/fr/universite/campus_et_sites/a_paris_et_en_idf/campus_jussieu2.html

Le pot se déroulera en salle 101 (barre 26-00).

=========
Abstract
=========
Traceroute is the most popular tool to discover the path
between two machines in the internet. Uses range from the diagnosis of network
problems to the assemblage of internet maps. It works under the
assumption that
just one single path exists between a pair of end-hosts, at any given time.
However, most commercial routers have load balancing
capabilities. If network administrators turn this feature on,
then a stream of packets from a source to a destination can follow
different paths. Under load balancing, traceroute suffers from two
deficiencies. First, it measures inaccurate paths, inferring
a number of false links and measurement artifacts. Second, it is unable to
detect all the available paths. For traceroute users, the consequences
are serious. Network operators diagnose wrong paths, while researchers
assemble and work on buggy internet maps.

This thesis presents a new traceroute implementation, called Paris traceroute,
which solves classic traceroute's problems under load balancing. By
maintaining
a constant flow identifier (defined as the 5-tuple: source and
destination addresses and ports, and protocol), it measures accurate paths,
therefore avoiding a majority of measurement artifacts caused by load
balancing.
In addition, its adaptive probing algorithm reports complete paths under
load balancing, while classic traceroute sends too few probes to have even a
moderate indication of the presence of load balancing.

We use Paris traceroute to characterize the extent of the deployment of
load balancing in today's internet. Our measurement study from
hundreds of source machines to thousands of destinations reveals that
50\% of the source-destination pairs traverse a per-flow load balancer.
A large number of core networks take advantage of load balancing capabilities.
As a result, the multipath routes that we observe generally span a few hops
in a single network, and consist in parallel physical links between
pairs of routers.
Furthermore, those parallel paths generally offer similar properties
(e.g. almost identical
delays).
These findings dramatically contrast with the traditional model
of an internet path, and should prompt researchers to take load balancing into
account in their future work.

=========
Keywords: Internet measurements, internet topology, traceroute,
load balancing, multipath routing.
=========

=========
Résumé
=========
Traceroute est l'outil le plus couramment utilisé pour découvrir le
chemin entre
deux machines sur internet. Il permet aussi bien de diagnostiquer des pannes
réseau que d'assembler des cartes d'internet. Il opère en partant du principe
qu'il n'existe qu'un seul et unique chemin entre deux machines distantes, à
tout moment. Cependant, la plupart des routeurs actuels présentent des
possibilités
de répartition de charge. Si les opérateurs réseau activent cette
fonctionnalité,
alors un flot de paquets transitant d'une source vers une destination peut
suivre différents chemins choisis par le routeur répartissant la charge.
En présence de répartition de charge, traceroute présente deux graves
défaillances.
D'une part, il mesure des chemins inexacts, en inférant de nombreux
faux liens et
autres artefacts de mesure. D'autre part il est incapable de détecter tous les
chemins possibles. Pour les utilisateurs de traceroute, les conséquences sont
graves. Les opérateurs réseau diagnostiquent des pannes sur de mauvais
chemins, tandis
que les chercheurs assemblent et travaillent sur des cartes comportant
des erreurs.

Cette thèse présente une nouvelle implémentation de traceroute, nommée
Paris traceroute, qui résout les problèmes rencontrés par le
traceroute classique en présence de répartition de charge. En maintenant
constant l'identifiant de flot des sondes qu'il émet (un identifiant
de flot est défini
par le 5-tuple: adresses et ports source et destination, et
protocole), il mesure
des chemins exacts, et donc il évite la majorité des artefacts de mesure
causés par les répartiteurs de charge. De plus, son algorithme de traçage
adaptatif découvre des multichemins complets en présence de répartition de
charge, alors que le traceroute classique émet trop peu de sondes pour avoir
une indication raisonnable de la présence de répartition de charge.

Nous utilisons Paris traceroute pour caractériser l'ampleur du déploiement
de la répartition de charge dans l'internet actuel. Nos campagnes de mesures
effectuées depuis des centaines de machines sources, vers plusieurs
milliers de
destinations, révèlent que 50\% des paires source-destination traversent un
répartiteur de charge par flot. Un grand nombre de réseaux de coeur
tirent partie
des capacités de répartition des routeurs. En conséquence, les multichemins
que nous observons s'étendent généralement sur quelques sauts au sein
d'un système autonome donné, et consistent en des liens parallèles
entre deux routeurs. De plus, ces chemins parallèles présentent
généralement des
propriétés similaires, par exemple, des délais pratiquement identiques.
Ces résultats contrastent de façon significative avec le modèle traditionnel
d'un chemin internet, et devraient inciter les chercheurs à prendre en compte
l'existence de la répartition de charge dans leurs travaux futurs.

=========
Mots-Clés : Mesures de l'internet, topologie de l'internet, traceroute,
répartition de charge, routage multichemins.
=========

========
Jury
========
- Jean-Jacques PANSIOT, Professeur, Université de Strasbourg (Rapporteur)
- Olivier BONAVENTURE, Professeur, Université catholique de Louvain
(Rapporteur)

- Matthieu LATAPY, Chercheur CNRS, UPMC Sorbonne Universités (Examinateur)
- Martin MAY, Chercheur, Thomson Labs (Examinateur)
- Abdelhamid MELLOUK, Professeur, Université Paris-Est Créteil, (Examinateur)

- Serge FDIDA, Professeur, UPMC Sorbonne Universités (Directeur)
- Timur FRIEDMAN, Maître de Conférences, UPMC Sorbonne Universités (Encadrant)
- Renata TEIXEIRA, Chercheuse CNRS, UPMC Sorbonne Universités (Encadrante)

Cordialement,

Brice Augustin