A propos de la difficulté du routage égal par plus courts chemins

Les réseaux de communications sont devenus très complexes de nos jours. Cependant, depuis leur tout début avec ARPANET, les chercheurs et les ingénieurs ont conçu plusieurs protocoles aux divers équipements de ces réseaux afin de réduire cette complexité et d'atteindre la meilleure performance possible du réseau. OSPF ("Open Shortest Path First") est l'un des plus anciens protocoles qui ont tenu bon avec cette évolution. Il appartient à la sous-famille des protocoles de routage. Le but d'un protocol de routage est de rendre chaque routeur capable de décider, à chaque paquet recu, le prochain routeur voisin à qui ce paquet doit etre transmis. Quand le protocole de routage activé sur le réseau est OSPF, tout les paquets suivent des plus courts chemins pondérés, ou les poids (à voir comme des longueurs) sont fixés par l'administrateur réseau. Quand ces poids sont définis de manière à avoir plusieurs plus courts chemins pour une paire de noeuds, le routage dépendra de la règle qui est implémentée avec OSPF. Il y a plusieurs règles permettant de balancer le trafic entre les différents plus courts chemins, et l'une des plus connues est ECMP ("Equal Cost Multiple Path"): un noeud qui a plusieurs liens sortant sur le plus court chemin envers une destination d divisera le trafic qui lui arrive et qui est destiné à d de manière égale entre tous les chemins. Si le trafic nécessite de ne pas être partagé entre différents chemins, les poids doivent etre affectés de manière à ce que pour chaque paire de noeuds il y ait un unique plus court chemin. Afin de comprendre la difficulté du routage OSPF, nous avons regardé un problème assez simple, mais qui reste fondamental, où le but est de maximiser le débit quand une seule et unique paire de noeuds com- munique des données sur le réseau. A notre meilleure connaissance, ce problème a été prouvé NP-complet, utilisant une réduction au problème de la couverture d'un ensemble, et aucune approximation, avec garantie non trivial, n'a été proposée jusqu'à présent. Nous montrons, en utilisant une réduction différente que ce problème ne peut être approximée à un facteur constant et nous donnons une approximation qui dépend de la plus longue distance du graphe