OPTIMISATION DANS LES RÉSEAUX DE TÉLÉCOMMUNICATIONS

De nombreux problemes d'optimisation se posent dans les reseaux de telecommunications. Pour les resoudre, on utilise souvent les outils de la theorie des graphes. Un graphe est constitue d'un ensemble de sommets qui modelisent les noeuds et d'un ensemble d'aretes qui modelisent les liens du reseau. Les noeuds peuvent etre les abonnes ou utilisateurs du reseau mais aussi des equipements comme des ordinateurs, serveurs, routeurs, antennes, des pages Web... Les liens peuvent etre des liens physiques (câbles, fibres), des liens radio voire des liens virtuels comme les liens hypertextes. Le role des reseaux de (tele)communications est notamment d’echanger de l’information. Par exemple, un mail entre deux personnes, le chargement d’une video a partir d’un serveur ou l’acces a une page web sont appeles des requetes entre deux nœuds d’un reseau. Router une requete consiste a trouver dans le graphe representant le reseau un chemin entre les deux nœuds qui communiquent. Par exemple, dans la Figure 3(a), une requete entre les nœuds s et t est routee par le plus court chemin de longueur 2 (via le sommet a). Trouver un chemin fait partie des problemes dits « faciles ». Ils peuvent etre resolus en temps polynomial en la taille du reseau (voir l’article « TRANSPORT, FLOTS ET COUPES »). Dans la realite, plusieurs requetes doivent etre routees simultanement, en satisfaisant de nombreuses contraintes (capacite ou bande passante limitee, interferences, traitement des informations,...). Ceci rend les problemes bien plus compliques. Nous presentons des problemes de conception du reseau et de gestion via divers exemples en nous focalisant sur leurs applications, leur description, et leur modelisation sous forme de problemes de graphes.