Ces 15 dernières années, le monde des télécommunications a connu plusieurs bouleversements très importants : la mise en concurrence des opérateurs, le développement très rapide de la téléphonie mobile et l’hégémonie du réseau Internet comme support fédérateur de tous les futurs services de communication. Ces bouleversements ont obligé les opérateurs historiques à adapter très rapidement leurs modes de fonctionnement et les nouveaux entrants à découvrir de nouvelles activités.
On s’intéressera dans cet exposé à l’impact de l’introduction des technologies IP sur les problématiques traditionnelles d’optimisation de réseau. En particulier, les modèles "classiques" ont du être considérablement modifiés afin de pouvoir prendre en compte, les spécificités du routage Internet, des principes de Qualité de Service (QoS) inhérents au mode paquet, de nouveaux modes de sécurisation, etc…

12h00 - 13h50

DÉJEUNER

 Les réseaux de télécommunications peuvent être vus comme la superposition de plusieurs couches. Deux couches consécutives ont une relation client-serveur. L’une demande un service et l’autre l’exécute. Si l’on considère par exemple, une technologie IP/MPLS sur optique, le trafic qui semble être routé sur la technologie MPLS (couche cliente) est en fait routé sur la couche de transport optique.
Cette nouvelle infrastructure multicouche nécessite une sécurisation et un dimensionnement appropriés et donne lieu à de nouveaux problèmes d’optimisation.Cette nouvelle infrastructure multicouche doit être suffisamment fiable afin de pouvoir reconstituer le trafic en cas de panne. De plus, ces réseaux  doivent disposer de capacités suffisantes afin que les demandes puissent être écoulées entre les sommets origine-destination.
Dans cet exposé, nous considérerons le problème de sécurisation multicouche avec capacités du réseau IP. Ce problème s’intéresse à une représentation en deux couches consécutives IP-sur-optique.
Nous donnerons deux formulations arc-sommet et arc-chemin du problème, sous la forme de programmes linéaires mixtes. Nous présenterons de nouvelles classes d’inégalités valides pour les deux formulations ainsi que des procédures de séparation associées à ces contraintes. Nous présentons un algorithme de coupes et branchements pour résoudre le problème à l’aide de la formulation arc-sommet. Nous présenterons également une méthode de génération de colonnes développée dans le cadre d’un algorithme de coupes et branchements pour la formulation arc-chemin. Nous discutons enfin de certains résultats expérimentaux. Ceux-ci sont obtenus à partir de données réelles fournies par France Télécom.

L’étude des grands réseaux d’interactions tels que le réseau Internet, des réseaux sociaux ou biologiques, passe souvent par une première phase de collecte des donénes. Bien que ce processus de mesure soit générallement considéré comme fiable, il a été montré récemment qu’il engendre souvent une vision du réseau non seulement partielle mais aussi pouvant être fortement biaisée. L’étude du biais engendré par la mesure, ainsi que les moyens de le maîtriser, est nommé métrologie.
En utilisant un modèle simple du processus de mesure du réseau Internet, nous montrerons que les méthodes utilisées pour explorer un réseau à l’aide de plus courts chemins peuvent fortement influencer l’observation. Nous montrerons aussi, à l’aide d’un certain nombre de simulations, dans quelle mesure on peut espérer de meilleurs résultats en augmentant le nombre de points de mesure dans le réseau.

La construction d’une structure connectant dans un réseau un sous-ensemble de membres est un problème classique. On peut en effet évoquer toute forme de réunion dans un réseau, où les membres veulent échanger des données via une structure dédiée. Néanmoins, dans ce type de rassemblements virtuels, il n’est pas toujours possible de connaître les données du problème à l’avance : les membres peuvent arriver ou partir à tout moment (version dynamique du problème). Par exemple, dans les systèmes pair à pair, il est inconcevable de prédire qui va communiquer avec qui. Les échanges se font "au fil de l’eau". Les membres à connecter et à déconnecter sont alors dévoilés au fur et à mesure (modèle online). Cette situation peut être modélisée sous la forme du problème de graphe suivant. Le but est de construire au fur et à mesure une structure couvrante (un arbre) sur le graphe sous-jacent, en garantissant une qualité de service satisfaisante en terme de délais d’acheminement des données point à point. Nous avons choisi de traduire cette exigence de qualité sous la forme du problème d’optimisation suivant : nous devons maintenir tout au long de la réunion un arbre qui minimise la distance maximum et moyenne entre les membres du groupe (correspondant au temps de communication maximum et moyen entre les membres).

L’objectif de cet exposé est de donner un aperçu, au travers d’exemples, de la variété des problèmes d’optimisation combinatoire que nous rencontrons dans le cadre de la conception d’autocommutateurs utilisés en téléphonie mobile cet exposé consistera donc essentiellement en la présentation d’applications de techniques algorithmiques connues à des problèmes concrets : résolution de problèmes de flots et configuration dynamique de processeurs de traitement d’appels, résolution de problèmes de couplages et configuration de cellules radio, résolution de variantes du problème de bin-packing et gestion des liens entre deux autocommutateurs, résolution de problèmes de sac à dos max-min et passage en mode dégradé d’un équipement, etc. Nous insisterons sur les contraintes, principalement liées au temps réel, qui restreignent le champ des méthodes de résolution utilisables, en particulier lorsque nous nous trouvons confronté à des problèmes NP-difficiles.