∈ P ⊂ R m , (1)
Comme A est immense, on utilise un algorithme de plans coupants qui ajoute les contraintes une par une. À chaque itération it ≥ 1, cet algorithme construit une approximation extérieure P it ⊃ P ; grâce au sous-problème de séparation, il coupe la solution optimale opt (P it ) pour construire une approximation extérieure plus fidèle P it+1 de P. On construit ainsi une séquence d'approximations : P 1 P 2 P 3 • • • P p ⊇ P. L'algorithme s'arrête lorsqu'il devient impossible de séparer opt (P it ), ce qui signifie que max b opt (P it ) = b opt (P).

La méthode des points intérieurs (IPM, en abrégé, pour « Interior point method ») a été publiée en 1984 par N. Karmakar et elle a été un « breakthrough » qui a revitalisé l'étude des PL. Il s'agissait du premier algorithme à la fois théoriquement polynomial et capable de rivaliser en pratique avec l'algorithme du Simplexe. Dans cet étude on va utiliser la famille d'IPM appelle « primal-dual IPM » qui sont parmi les plus efficaces en pratique. Je préfère citer [START_REF] Nocedal | Chapitre 14, Numerical optimization[END_REF] : « By the early 1990s, a subclass of interior-point methods known as primal-dual methods had distinguished themselves as the most efficient practical approaches, and proved to be strong competitors to the simplex method on large problems. ».

Il existe déjà plusieurs travaux qui utilisent une IPM pour déterminer la solution optimale opt (P it ) à l'itération courante it, voir par exemple les travaux initiés par Jacek Gondzio au milieu des années 1990 [START_REF] Gondzio | Warm start of the primal-dual method applied in the cutting-plane scheme Mathematical Programming[END_REF]. En fait, il n'est même pas obligatoire d'exécuter l'IPM jusqu'à sa fin pour déterminer opt(P it ) : l'algorithme plus général de plans coupants peut se « contenter » d'une solution sous-optimale de P it et d'appeler le sous-problème de séparation sur celle ci. L'avantage des « dual-primal IPM » est qu'il est possible d'avoir un contrôle sur une mesure de dualité µ (cf. page suivante) entre une solution primale et une solution duale. Donc il est possible d'arrêter l'IPM lorsque la mesure de dualité est très petite, ce qui signifie que la solution sous-optimale courante n'est pas trop éloigné de opt(P it ). De toute façon, si cette solution sous-optimale peut être séparée, l'algorithme de plans coupants peut continuer normalement.

Je suis en train d'étudier une approche pour (essayer de) surmonter l'inconvénient suivant : Si on utilise une IPM pour déterminer opt(P it ) à l'itération it, les points intérieurs calculés par l'IPM seront intérieurs par rapport à P it , mais pas forcement intérieurs par rapport à P, car P it ⊃ P. C'est dans ce sens que je qualifie (dans le titre) la méthode proposée de « Globally-Interior Point ». Les points intérieurs générés seront intérieurs par rapport à P et pas seulement par rapport à P it . L'outil principal utilisé pour s'assurer que l'IPM exécuté à l'itération it ne sort pas de P est le sous-problème de projection présenté dans [START_REF] Porumbel | Projective Cutting-Planes[END_REF]. Étant donné un y ∈ P et une direction d ∈ R m , ce sous-problème demande de déterminer la longueur de pas maximale t tel que y+t•d ∈ P. J'ai présenté dans [START_REF] Porumbel | Projective Cutting-Planes[END_REF] et dans un « follow-up work » plusieurs algorithmes pour résoudre ce sous-problème dans diverses contextes ; le code est déjà fonctionnel et disponible en ligne.

Pour pouvoir utiliser la plate-forme IPM, on doit réécrire (1) sous la forme : max y,s b y tel que : A y + s = c, s ≥ 0 n , où A ∈ R m×n . Chaque colonne de A représente une contrainte écrite dans (1) sous la forme a y ≤ c a . On considère que n augmente (d'une unité) à chaque itération it de l'algorithme général de plans coupants ; m est toujours fixe. Pour un n et un m fixés à une itération donnée it, l'IPM vise à déterminer les vecteurs x, y et s qui satisfont :

A y + s = c (2a) Ax = b (2b) x i s i = 0 ∀i ∈ [1..n] (2c) (x, s) ≥ 0 n (2d)
Une IPM converge vers une solution de ce système en construisant une séquence de solutions primales-duales (x k , y k , s k ) qui satisfont la contrainte (2.d) de manière stricte, i.e., x k i , s k i > 0. La contrainte (2.c) n'est jamais forcement imposée par un IPM, mais on a la garantie que la mesure de dualité

µ k = 1 n n i=1 x k i s k i converge vers 0 lorsque k → ∞.
À chaque itération k, l'IPM résout un système d'équations qui lui permet de calculer le pas Newton (∆x k , ∆y k , ∆s k ) pour passer à l'itération suivante :

(x k+1 , y k+1 , s k+1 ) = (x k , y k , s k ) + (∆x k , ∆y k , ∆s k ). (3)
L'algorithme proposé ici intègre (3) dans un contexte de plans coupants. Il démarre en fait avec une forme réduite de (2) où on a très peu de colonnes (un très petit n). Avant d'appliquer (3), on appelle le sous-problème de projection pour garantir que (3) ne mène pas à une solution y k+1 qui sort de P. Ce sous-problème détermine le pas maximal t tel que y k + t • y k ∈ P ainsi qu'une contrainte saturée par y k + t • y k , qui est aussi une nouvelle colonne à insérer dans la matrice A pour augmenter sa taille de n à n + 1. Une difficulté importante c'est de s'assurer que la contrainte ( Par la suite, j'ai étudié le problème de coloration de graphe. C'est plus difficile d'ajouter deux colonnes complémentaires à la fois, car le complémentaire 1 m -a stab d'un stable a stab ∈ {0, 1} m est un vertex-cover. Je pense m'orienter sur la résolution d'un nouveau problème de génération de colonnes où les colonnes seront associées à la fois aux stables et aux minimal vertex-covers.

Daniel Porumbel 1

 1 CEDRIC, CNAM, Paris, France daniel.porumbel@cnam.fr Mots-clés : l'algorithme des points intérieurs, projection dans des polytopes avec un nombre exponentiel de contraintes 1 Le contexte Soit un programme linéaire (PL) défini par un nombre immense de contraintes A : max y b y : a y ≤ c a , ∀(a, c a ) ∈ A = max y b y : y

  2.b) reste satisfaite après cette extension. Pour cela, on propose d'ajouter deux colonnes à la fois, une colonne légitime a new et une colonne (artificielle ou naturelle) complémentaire a new = ba new . Il suffit ensuite de multiplier x avec t < 1 et d'élargir ce x avec deux positions de valeur 1 -t qui correspondent à ces deux colonnes a new et a new de A. 3 Tests numériques et conclusions D'abord, j'ai étudié le problème affiché comme exemple sur la fiche Wikipedia de l'IPM : max y 1 + y 2 : 2p • y 1 + y 2 ≤ p 2 + 1, ∀p ∈ [0, 1 z , 2 z , 3 z , . . . 1], où z peut être très élevé. Ce problème vérifie la propriété indiquée plus haut : si a new = [2p, 1] est une colonne légitime, la colonne complémentaire a new = [2(1 -p), 1] l'est aussi. Le nombre de pas de la nouvelle méthode augmente beaucoup mois vite que celui de l'algorithme de plans coupants (lorsque z → ∞).


Daniel Porumbel
email: daniel.porumbel@cnam.fr

Is there any O(2 n ) algorithm your OS can run in almost no time ?

If you think it's simple, then you have misunderstood the problem.

Bjarne Stroustrup (concepteur C++), 1997

La vérité n'est pas une fille qui saute au cou de [celui] qui ne la désire pas ; c'est plutôt une fière beauté, à qui l'on peut tout sacrifier, sans être assuré pour cela de la moindre faveur.

Le piège

Si vous pensez que la réponse à la question du titre doit être « Non, c'est complètement impossible ; ça serait une hérésie contre le bon sens de l'informatique fondamentale ! », pensez aussi à ne pas oublier la devise de cette communication. D'ailleurs, les deux citations signifient la même chose : la réalité et la pratique peuvent être parfois si complexes qu'elles échappent aux systèmes de valeurs et aux axiomatisations avec lesquelles la théorie nous a habitué.

Les deux programmes ci-après exécutent les mêmes instructions (pour faire de la programmation dynamique). Le code a été aligné pour voir clairement la correspondance ligne par ligne. #include<i o s t r e a m > u s i n g namespace s t d ; i n t main ( ) { i n t n = 3 0 ; i n t z = 1<<n ; // 2^n z++; i n t * tab=( i n t * ) m a l l o c ( z * s i z e o f ( i n t ) ) ; f o r ( i n t i =0; i <z ; i ++) Les deux programmes ont été compilé avec g++ sans option d'optimisation. Le code à gauche prend environ 0.75 secondes pour n = 28, 1.5 secondes pour n = 29 et 3 secondes pour n = 30. Cela suit donc une loi exponentielle qui correspond à la complexité attendue de O(2 n ). Maiscroyez le, croyez le pas -le programme à droite prends environ 0.001 secondes pour n = 30 sur ma machine. Le cas n ≥ 31 échoue dans les deux cas ; cela est discuté au point 2) ci-dessous.

tab [ i ] = 0 ; f o r ( i n t i =0; i <n ; i ++) i f ( tab[1<<( i +1) ] < 7 + tab[1<< i ] ) tab[1<<( i +1) ] = 7 + tab[1<< i ] ; cout<<tab [ z-1]<< e n
Le goulet d'étranglement vient de l'initialisation du tableau tab de 2 n + 1 cases. On doit aborder ce « détail d'implémentation » pour répondre à la question (théorique) tu titre. Le programme à droite n'a pas vraiment initialisé la zone de mémoire associée au tableau tab (environ 4GB) en une milliseconde. Il peut avoir plusieurs explications : 1) Le système d'exploitation (OS) a pu faire l'initialisation mémoire en préalable. Certains OS utilisent leur « idle time » pour remplir toute la mémoire disponible avec des zéros. Cela sert à garantir que les données d'un processus terminé ne peuvent pas être récupérées plus tard par un autre processus. Après investigation, mon OS n'a pas fait cela, mais cette fonctionnalité existe dans d'autres OS. Cela nous amène à une question que la théorie seule ne pourra jamais résoudre à mon avis : quelle est la complexité d'un algorithme si on sait qu'une partie de son code est (anticipé par l'OS et) exécuté en préalable avant son lancement ?

2) L'OS a pu faire une initialisation qu'on pourrait qualifier de « lazy ». C'est connu que certains processus demandent de la mémoire qu'ils n'utilisent pas toute de suite. Ainsi, l'OS a donné juste une forme de promesse de mémoire initialisée. Dès que le processus a réellement besoin d'utiliser une case mémoire, le processeur déclenche un « page fault » et le noyau intervient pour attribuer de la vraie RAM. 1 Si l'appel calloc(...) échoue pour n ≥ 31, c'est parce que l'OS ne veut pas s'engager sur une allocation de mémoire qu'il ne peut pas assurer. Mais il est possible de concevoir un système de gestion de mémoire qui pourrait donner de la mémoire fictive même pour n ≥ 31, étant donné qu'on sait que le programme va toucher au maximum O(n) cases. On obtient un nombre de "page faults" à gérer de maximum O(n).

3) Le compilateur a pu être très astucieux, car on ne retrouve pas la même vitesse si on remplace g++ avec gcc. La performance se dégrade aussi si on remplace calloc avec la méthode C++ d'initialisation, c.à.d., avec new int[z](). La situation se complexifie si on commence à utiliser des options d'optimisation. Comme toute vérité, il est possible d'éplucher cette question comme un chou avec milles feuilles. Mais je peux pas aller plus loin dans un résumé de 2 pages.

Nonobstant, pour moi il est clair que je ne peux par répondre à la question du titre par un simple « Oui » ou par un simple « Non ». C'est plus complexe et nuancé que ça.

Conclusion et perspectives

Prenons une perspective plus haute pour saisir le problème plus général : beaucoup d'aspects de la vie réelle échappent trop facilement à ceux qui raisonnent que sur la base de la théorie ou que sur la base d'informations synthétiques, y compris à certains rapporteurs (des revues, jurys de thèse, etc). J'ai déposé à youtu.be/YuKnE6zH-J8 une démonstration d'un programme qui peut devenir 7-8 fois plus rapide si on ajoute un simple appel cplex.end() à la fin d'une fonction. Même en supposant un monde que avec des gens très très honnêtes, il est facile de se tromper soi même dans un tel cas et de penser que c'est une contribution théorique (ex, une nouvelle inégalité valide) qui a rendu l'algorithme 7-8 fois plus rapide -alors que cela ne vient que d'un simple cplex.end() oublié par un collaborateur.

J'ai déjà abordé ce sujet dans une suite de travaux que je présente à la Roadef depuis 3 ans. Le premier papier (Roadef 2019) commence avec cette question de vitesse d'exécution.

La vitesse d'exécution de tout algorithme pratique dépend d'un facteur constant de complexité γ étroitement lié à la qualité de l'implémentation. Je présente des communications à la Roadef depuis dix ans et je viens seulement de réaliser que tous mes exposés se terminent invariablement avec une phrase comme « Pour finir, je vais vous épargner les détails d'implémentation parce que je préfère me focaliser sur l'essentiel et sur les concepts de haut niveau ». Malgré ses mérites, cette phrase est trop simpliste. Elle peut détourner le lecteur d'attention moyenne de certaines vérités. Comme une porte dérobée dans un logiciel, une conséquence inavouée est la suivante : le cout en temps de calcul est très peu impacté par (le facteur constant de complexité associé à) la qualité de l'implémentation et on peut l'ignorer. Ce facteur constant γ est aussi invisible lorsqu'on calcule des complexités théoriques comme O(n 2 ), O(2 n ), etc. Mais imaginez un vendeur qui dirait que le coût à payer serait de 1000e multiplié par un facteur constant γ = 3 ou γ = 6 qui n'a aucune importance dans l'absolu. Si cela puisse être vrai pour certains, je suis heureux que mon destin m'a épargné le vide d'une existence dans un luxe si démesuré.

Le papier 2021 se conclue avec une citation de Christopher Strachey (Oxford, vers 1970) :

It has long been my personal view that the separation of practical and theoretical work is artificial and injurious. Much of the practical work done in computing is unsound and clumsy because the people who do it have not any clear understanding ofthe fundamental design principles of their work. Most of the abstract mathematical and theoretical work is sterile because it has no point of contact with real computing. One of the central aims of the Programming Research Group as a teaching and research group has been to set up an atmosphere in which this separation cannot happen.

Ce résumé s'inscrit donc dans un travail plus conséquent, composé de plusieurs papiers (Roadef ou autre) déposés à cedric.cnam.fr/~porumbed/soft/. Si j'ai décidé de prendre la plume pour y écrire plusieurs pages, ce n'est pas pour renforcer des idées bien connues en utilisant une nouvelle phraséologie ou des arguments plus originaux. C'est plutôt pour remettre en question quelques présupposés très fallacieux et très répandus en RO et informatique.

  * tab=( i n t * ) c a l l o c ( z , s i z e o f ( i n t ) ) ; // r e c a l l c a l l o c r e t u r n s by d e f a u l t // a memory b l o c k f i l l e d with z e r o s f o r ( i n t i =0; i <n ; i ++) i f ( tab[1<<( i +1) ] < 7 + tab[1<< i ] ) tab[1<<( i +1) ] = 7 + tab[1<< i ] ; cout<<tab [ z-1]<< e n d l ; // always 7 * n }

1.

  Voir la réponse de Dietrich Epp sur le forum de questions stackoverflow.com/questions/ 2688466/why-mallocmemset-is-slower-than-calloc ou aussi cs.stackexchange.com/questions/83834/ what-is-the-time-complexity-of-memory-allocation-assumed-to-be


Cette communication porte sur les difficultés qui apparaissent sur le point de contact entre la programmation et la théorie. C'est sur ce point de contact que la courroie de transmission (de la force intellectuelle) perd une borne partie de son énergie lors de la résolution d'un problème d'optimisation. Il n'est pas toujours si facile de traverser la frontière entre le pays de la programmation et le pays de la théorie ; qu'est-ce qui fait que la vie d'un travailleur frontalier est plus difficile qu'il n'y paraît à première vue ?

Les conditions de vie dans ces deux pays exigent des traits intellectuels assez différents et parfois des vocations scientifiques presque opposées ; et en plus, il faut s'adapter à chaque fois qu'on traverse la frontière. Par ailleurs, les gens les plus attachés à la théorie ont une compréhension très approximative de la programmation et du génie logiciel ; ils pensent que la programmation « c'est de la cuisine ; ça fait partie des petites choses qui doivent être faites pour obtenir des résultats ». Tant que cette vue reste au pouvoir, la communauté sera fracturée : (a) D'un coté, des sommités académiques qui n'ont jamais vu un algorithme en exécution peuvent manquer de profondeur dans leur réflexions ; par exemple, leur discours se focalisent souvent sur les « grandes idées », sans réaliser que la dynamique et l'efficacité d'un algorithme peut facilement changer si on modifie un « petit » paramètre ou même si on introduit une contrainte redondante dans le modèle. J'ai peur qu'ils se bornent souvent à essayer de tout comprendre en gros. Et il est impossible de pénétrer au coeur d'une telle question si on l'étudie à partir des hauteurs d'une théorie (simplificatrice). Cela les conduit à toute sorte d'erreurs d'approximation dans leur jugement et dans leurs évaluations. Qu'on ne s'illusionne pas : quiconque n'a jamais lutté avec une machine pour contrôler la dynamique d'un algorithme ne connaitra jamais les secrets de l'algorithmique au delà de certaines généralités simplificatrices. (b) D'un autre coté, les programmeurs qui voient tous les jours des algorithmes en exécution n'ont pas toujours -surtout les très jeunes -l'esprit de synthèse et les bonnes grilles d'analyse pour déconstruire certains pièges du système. Cela les empêche d'avoir une vision globale très correcte sur la place et la valeur de leur travail dans un contexte scientifique plus général. Ces idées non-techniques se projettent de milles façons sur le plan technique. On doit souvent choisir (a) ou (b). Beaucoup pensent que la théorie est si noble que la programmation doit rester une affaire secondaire par rapport à la « recherche fondamentale ». Je pense que cela s'applique parfaitement aux 1% meilleurs chercheurs théoriques qu'on doit pas embêter avec des problèmes d'implémentation. Mais l'histoire n'est pas si rose ou si simple pour les autres 99%. Ils évitent souvent les questions d'implémentation pour des raisons très prosaïques : il faut prendre des instances, lancer des tests, se replonger dans le code à chaque révision ; bref, c'est trop fastidieux. En conséquence, beaucoup se disent : je vais chercher (une niche dans) une théorie. Et si j'arrive à bien m'entendre avec les quelques dizaines de chercheurs qui travaillent sur cela, ça sera que du bonheur. Et je vais pouvoir aussi appeler mon travail « recherche fondamentale ». J'étais à deux doigts de tomber dans ce piège. Ma liste de publications comporte un petit article sur un algorithme sans implémentation dans la théorie des fonctions sous-modulaires [1]. À l'époque, je me suis dit : « la théorie de ces fonctions a l'air chouette, on a pu gagner le prix Fulkerson (en 2003) pour des travaux là dedans, tout est très noble ; j'aurai du pain sur la planche toute ma vie quoi qu'il se passe ». Mais, non, c'était un piège ! Un jour j'ai compris que j'étais inconsciemment à la recherche d'une planque, c.à.d., une niche (lisez : une place au soleil) parmi les innombrables théories que l'humanité a conçues. Comme je ne fait pas partie des 1% des gens les plus forts sur les aspects théoriques, j'ai compris qu'une autre loi régira ma vie : ceux qui choisissent une planque finissent au placard (de leur discipline au sens large).

Cela m'a poussé à éviter les niches théoriques pour me placer sur un domaine qui touche plus de monde : la frontière entre la théorie et la programmation. Il ne faut pas comprendre que je veux fuir la théorie. J'ai écrit 100 pages sur la théorie de l'optimisation sémipositive définie ou SDP [2], une théorie plus complexe que la programmation linéaire (en nombre entiers). Mais je ne pense qu'à trouver un jour les moyens de la connecter à la programmation. Je ne cherche pas, par exemple, à l'utiliser pour concevoir des algorithmes théoriques d'approximation (genre Goemans-Williamson). Je ne veux donc m'éloigner ni de la théorie ni de la programmation. Un travail issu d'un cerveau composite, où une personne fait la théorie et une autre l'implémentation, ne peut avoir qu'une importance secondaire dans mon coeur.

Concernant cette pratique, je parle à dessein comme si c'était une affaire de coeur, pour être clair que j'émets ici un avis purement personnel. Je pense que cette pratique mène à une société fracturée et refroidie qui évolue comme un enfant dans un orphelinat : même le service technique le plus brillant ne peut pas compenser la démoralisation qui résulte du manque d'intérêt véritable pour le travail de programmation. Mais on peut faire abstraction de cet obstacle artificiel : la notion d'alliage théorie-programmation à l'intérieur d'un seul cerveau trouvera un jour tout son sens, beaucoup plus que de nombreuses niches théoriques. Ceci n'est pas un conseil à tout-và pour tout le monde. C'est juste une idée qui sera, je l'espère, un jour utile à tous ceux qui se sentent aujourd'hui aussi perdus que j'étais il y a 10 ans. Je répète que je ne m'adresse pas aux 1% meilleurs chercheurs théoriques qui ont une vraie vocation pour leur théorie où ils sont irremplaçables. Je m'adresse, en suivant en peu la devise de ce résumé, juste à d'autres franc tireurs qui cherchent une autre relation avec la théorie.

En conformité avec la tradition Roadef, ce document de 2 pages n'est qu'un résumé d'un travail plus complet. Vous trouverez une version élargie de 3-4 pages à cedric.cnam.fr/~porumbed/ roadeffull.pdf ou une argumentation d'une dizaine de pages à [3].

J'ai déjà évoqué ces idées avec diverses confréres, à la Roadef ou ailleurs. Ils étaient tous souvent d'accord sur certains points. Mais je sentais que l'essentiel de mes idées glissaient sur eux comme de l'eau sur un canard. C'est vers la fin de mes recherches que j'ai eu le plaisir de trouver un allié dans le passé d'une des meilleures université du monde (Oxford), en la personne de Christopher Strachey (1916-1975). En fait, je ne peux peut-être pas dire que c'est mon allié, mais j'ai été réconforté par les mots ci-dessous qu'il a écrits il y a un 50 ans. J'espère que cela pourra se réitérer plusieurs (maintes) fois dans l'avenir, dans l'esprit de la devise de ce résumé.

It has long been my personal view that the separation of practical and theoretical work is artificial and injurious. Much of the practical work done in computing, both in software and in hardware design, is unsound and clumsy because the people who do it have not any clear understanding of the fundamental design principles of their work. Most of the abstract mathematical and theoretical work is sterile because it has no point of contact with real computing. One of the central aims of the Programming Research Group as a teaching and research group has been to set up an atmosphere in which this separation cannot happen.

Références

[ 1 ]

 1 Daniel Porumbel, Prize-Collecting Set Multi-Covering With Submodular Pricing, International Transactions in Operational Research, 25 (4) :1221-1239, 2018 [2] Daniel Porumbel, Demystifying the characterizations of SDP matrices in mathematical programming, report technique CNAM, http://cedric.cnam.fr/~porumbed/papers/sdp.pdf [3] Daniel Porumbel, D'un « petit détail » d'implémentation vers un manifeste sans limite (sur l'éloignement entre la programmation et la théorie), cedric.cnam.fr/~porumbed/soft/ 2

  D'un détail d'implémentation vers un nouveau regard sur l'interpénétration entre la théorie et la programmation Daniel Porumbel, CEDRIC-CNAM Toute vérité qu'un homme découvre et toute obscurité qu'il arrive à élucider intéressera un jour un autre esprit pensant ; peu importe quand il la comprendra, cela le réjouira et le consolera. C'est à un tel homme que nous parlons, tout comme ceux qui nous ressemblent nous ont parlé, et ont été notre consolation dans ce désert de la vie. Arthur Schopenhauer


Sur la place en RO des techniques pour rendre la programmation (avec cplex ou gurobi) plus facile Daniel Porumbel 1 CEDRIC-CNAM, 292 rue Saint Martin, Paris France daniel.porumbel@cnam.fr

Aspects techniques et code source

Je présente une réalisation logicielle d'environ 1000 lignes de code C++, conçue pour écrire plus facilement des algorithmes de plans coupants. Au début, j'ai pensé que je n'allais jamais présenter ce code dans une communication officielle. Mais un jour j'ai compris que de nombreux travaux peuvent bloquer plus facilement sur des questions d'implémentation que sur d'autres problématiques qui bénéficient de plus d'attention (comme la modélisation).

Il s'agit juste de deux fichiers CuttingPlanesEngine.cpp et CuttingPlanesEngine.h qui permettent de faire fonctionner le code à droite. La première moitie de ce code minimise : 23.7s avec cplex12.6 pour résoudre min

obj x : c x ≥ 4.2, x i ∈ [0, 100] ∀i ∈ [1..n]
x i : 2(x i + x j + x k ) ≥ 5∀i, j, k ∈ [1..n], n = 3500.
Le Makefile cherche tout seul le chemin d'installation cplex. Comme les deux fichiers CuttingPlanesEngine.h/.cpp ont 1000 lignes, ils offrent plusieurs fonctionnalités que je ne peux pas décrire ici. Le code complet est disponible à cedric.cnam.fr/~porumbed/cp.zip 2 Des aspects techniques vers des réflexions philosophiques D'abord, on peut se poser la question : pour quoi se permettre de sortir du cadre strictement technique pour s'intéresser à des aspects philosophiques sans impact sur le concret ? Le réponse est que l'impact réel puisse être plus important qu'on ne le pense. Un problème réel qui trouve la racine dans « la philosophie régnante de l'époque » a été bien décrit par un philosophe du 19 ème siècle [1], bien que certaines choses se sont améliorées depuis son époque : "... les fruits prennent le goût du sol sur lequel ils ont mûri. Ce qui est prôné hautement, publiquement, en tout lieu, est lu, et constitue en conséquence la nourriture intellectuelle de la génération qui se forme ; cette nourriture a l'influence la plus décidée sur la substance de cette dernière, et ensuite sur ses productions. Par suite, la philosophie régnante d'une époque détermine son esprit. Donc, si la philosophie du non-sens absolu domine, si des absurdités sans fondement et exposées en un langage d'aliénés passent pour de grandes idées, cet ensemencement produit une belle génération sans esprit, sans amour de la vérité, sans sincérité, sans goût, sans élan pour rien de noble, pour rien qui s'élève au-dessus des intérêts matériels, dont font partie aussi les intérêts politiques."

L'importance de la « philosophie régnante d'aujourd'hui » en informatique peut être analysée sous le prisme du texte ci-dessus. Revenons à la question de départ : quelle place pour des contributions d'implémentation dans la RO ? Mon intuition me dit qu'on nous fait souvent comprendre qu'il ne faut pas trop s'attarder sur ces aspects, comme s'ils n'étaient pas vraiment dignes de notre attention. Une telle conception de vie peut générer une fracture dans le monde scientifique, c.a.d, un clivage entre :

-des sommités académiques qui n'ont jamais vu un algorithme en exécution et qui se bornent à essayer de tout comprendre en gros. Ces personnes -surtout les très très âgéspeuvent manquer de contact avec le pays réel, un peu comme un très haut fonctionnaire.

-des programmeurs qui exécutent des algorithmes tout les jours mais qui n'ont pas toujours -surtout les très jeunes -les outils conceptuels et les bonnes grilles d'analyse pour déconstruire certains pièges du système, ce qui les empêche d'avoir une vision très large et exacte du domaine.

J'ai déjà abordé des questions similaires à l'édition précédente de la Roadef dans un article « Sur un détail d'implémentation : quelques idées pour accélérer l'exécution et la programmation C++ pour la RO » [2]. Cet article comporte que deux pages (la limite Roadef), mais je garde toujours en tête l'idée de le compléter pour faire une argumentation d'une douzaine de pages (qui sera déposé à http://cedric.cnam.fr/~porumbed/soft/). Je ne crois pas qu'il y aura beaucoup de gens (des hautes sphères) à me lire car l'histoire commencera comme ça :

  int n=5; //nb de v a r i a b l e s double o b j [ ] = { 3 , 3 , 3 , 6 , 8 } ; double c [ ] ={1 , 1 , 1 , 1 , 1 } ; // sepFunc : a f u n c t i o n / o r a c l e t o s o l v e t h e // s e p a r a t i o n sub-problem f o r a g i v e n x C u t t i n g P l a n e s E n g i n e c u t P l a n e s ( n , sepFunc ) ; c u t P l a n e s . setVarBounds ( 0 , 1 0 0 ) ; c u t P l a n e s . s e t O b j C o e f s M i n i m i z e ( o b j ) ; c u t P l a n e s . modelAddCut ( c , 4 . 2 ) ; c u t P l a n e s . s o l v e ( ) ; // c u t P l a n e s . t u r n A l l V a r s I n t e g e r ( ) ; cout<<" Obj␣ v a l ␣ b e f o r e ␣ c u t t i n g ␣ p l a n e s : " <<c u t P l a n e s . getObjVal ( )<<e n d l ; int i t e r s U s e d ; double time ; c u t P l a n e s . runCutPlanes ( i t e r s U s e d , time ) ; double f i n a l O b j = c u t P l a n e s . getObjVal ( ) ; cout<<" F i n a l ␣ o b j="<<f i n a l O b j <<" ␣ r e a c h e d ␣ a f t e r ␣ "<<i t e r s U s e d <<" ␣ i t e r a t i o n s . \ n " ; double * x = new double [ n ] ; c u t P l a n e s . g e t P r i m a l s ( x ) ; f o r ( int i =0; i <n ; i ++) cout<<" x [ "<<i <<" ]= "<<x [ i ]<< " ; ␣ " ;

"

  La vitesse d'exécution de tout algorithme pratique dépend d'un facteur constant de complexité δ étroitement lié à la qualité de l'implémentation. Je présente des communications à la Roadef depuis dix ans et je viens seulement de réaliser que tous mes exposés se terminent invariablement avec une phrase comme « Et pour finir, je vais vous épargner les détails d'implémentation parce que je préfère me focaliser sur l'essentiel et sur les concepts de haut niveau ». Malgré ses mérites, cette phrase est trop simpliste. Elle est de nature à éloigner le lecteur d'attention moyenne de certaines vérités. Comme une porte dérobée dans un logiciel, une conséquence inavouée est la suivante : le cout en temps de calcul est très peu impacté par (le facteur constant de complexité associé à) la qualité de l'implémentation et on peut l'ignorer. Ce facteur constant δ est aussi invisible lorsqu'on calcule des complexités théoriques comme O(n 2 ), O(n 2 logn), etc. Mais imaginer un vendeur qui dit que le coût à payer serait de 1000e multiplié par un facteur constant δ = 2 ou δ = 6 sans aucune importance ! Cela est peut-être vrai pour certaines personnes, mais je suis heureux que le destin de m'a épargné le vide d'une existence dans un luxe si démesuré." Références [1] Arthur Schopenhauer. La philosophie universitaire. (version numérisée par G. Heff, p. 61). www.schopenhauer.fr/oeuvres/philosophie-universitaire.html [2] Daniel Porumbel. Sur un « détail» d'implémentation : quelques idées pour accélérer l'exécution et la programmation C++ pour la RO. Le 20ème congrès annuel de la société Française de Recherche Opérationnelle et d'Aide à la Décision, Le Havre, 2019. cedric.cnam.fr/~porumbed/soft/ (une version de 12 pages y sera un jour déposée).


Daniel Porumbel
email: daniel.porumbel@cnam.fr

Demystifying the characterization of SDP matrices in mathematical programming

Cette communication s'adresse aux chercheurs (en programmation linéaire (en nombre entiers), meta-heuristiques ou d'autres branches de la RO) qui voudraient élargir leurs connaissances pour utiliser des techniques d'optimisation sémi-définie positive (SDP) dans leur travaux. 1 Plus exactement, je présente un travail d'environ 100 pages [1] qui permettra au lecteur d'acquérir les bases de ce domaine. J'ai réalisé ce travail principalement parce que je n'ai pas trouvé d'autre introduction à l'optimisation SDP qui cible le même public (voir Section 2).

Le manuscrit proposé devrait être accessible à tous ceux qui ne détestent pas les mathématiques, qui savent ce qu'est une dérivée et peuvent accepter sans preuve des résultats très basiques comme det(AB) = det(A) det(B). Si vous êtes dans ce cas, je pense vous pouvez comprendre ce manuscrit sans acheter d'autres livres. L'objectif primordial n'est pas de rappeler ou d'énumérer une liste de résultats, mais de faire le lecteur examiner (les preuves de) ces résultats, pour qu'il puisse développer une compréhension profonde du sujet.

Pour se lancer dans l'optimisation SDP, on pourrait naturellement être tenté de commencer par un livre consacré ou un « handbook of SDP ... ». Mais si le lecteur ne possède pas déjà des connaissances assez fraiches en mémoire sur les matrices SDP, je pense que cette voie, bien que basée sur d'excellentes intentions, risque d'être inaccessible. Un pas crucial pour comprendre la programmation SDP est la décomposition d'une matrice SDP en éléments propres ; c'est un concept que le néophyte ne devrait pas prendre à la légère, c.à.d, une lecture rapide d'attention moyenne serait insuffisante. Il suffit de regarder comment ces livres/handbooks présentent cette décomposition pour comprendre qu'ils ciblent un public tout simplement très différent (voir des détails en Section 2). Ce travail ne s'adresse pas non plus à ceux qui peuvent dire « Je me rappelle un peu la décomposition en éléments propres, car je l'ai fait en L3/M1 il y quelques n ≥ 5 ans ; pas besoin de preuve. » Je crains qu'une telle attitude ne vise que l'information, sans donner aucun moyen pour pénétrer dans l'essence des choses. De toute façon, mon cerveau fonctionne de la manière la plus opposée : j'aime tout apprendre en vérifiant les preuves par moi-même, dans le moindre détail si possible. Ainsi, les seuls résultats non prouvés dans ce manuscrit sont le théorème fondamental de l'algèbre et deux théorèmes dans section 5.3.2.3. Mais je fournis des preuves complètes pour, par exemple, la décomposition de Cholesky, le théorème de forte dualité pour la programmation linéaire conique (y compris SDP), six formulations équivalentes du nombre de Lovász, la formulation copositive du problème du stable, des résultats de convexification pour les programmes quadratiques et beaucoup d'autres.

J'ai essayé de tout prouver par moi-même, de sorte que certaines preuves sont originales bien que ce manuscrit n'a pas été conçu pour être un travail de recherche. Bien évidement, j'ai eu recours plusieurs fois à l'Internet, à des articles et à des livres, les références étant 1. Je n'ai pas soumis ce travail à un track de programmation non-linéaire, parce que cette communication ne s'adresse pas principalement aux chercheurs consacrés en programmation non-linéaire, convexe ou polynomiale, mais aux chercheurs/étudiants qui veulent découvrir le sujet pour la première fois, e.g., pour trouver des relaxations plus fortes que par relaxation linéaire.

indiquées sous forme de citations de notes de bas de page. J'ai essayé de tout simplifier autant que possible. Les briques de base sont présentées dans la première partie du manuscrit. Il est nécessaire de vraiment maîtriser les résultats de cette première partie avant de se lancer sur la deuxième partie ; en fait, ces briques de base pourraient être utiles si vous essayez de lire d'autres introductions plus avancées à la SDP. Le but de ce manuscrit est de vous donner tous les moyens pour pouvoir passer à un niveau supérieur et effectuer des travaux de recherche.

Une autre différence par rapport à la littérature consacrée officiellement est que ce travail n'est pas écrit par un expert de classe mondiale en programmation SDP, mais il sort tout simplement d'un cerveau qui a du lutter pour comprendre. Cela peut sembler n'être qu'une faiblesse, mais, paradoxalement, c'est à la fois une faiblesse et un avantage. Un avantage vient du fait que de nombreux experts tentent d'oublier les difficultés des débutants, ce qui, je l'espère, ne m'est pas arrivé. D'autres experts s'efforcent de rendre toutes les preuves aussi courtes que possible et de diminuer l'importance de certains résultats qu'ils ont vus des milliers de fois dans leur carrière. J'ai clairement évité cela ; en fait, bien que j'aie raccourci quelques preuves lorsque j'ai révisé ce manuscrit deux ans après la première esquisse, j'ai gardé d'autres preuves un peu trop longues pour viser une compréhension plus profonde du sujet.

Last but not least : si je n'essaie pas d'assumer un rôle d'expert mondial en programmation SDP c'est aussi pour éviter d'engager le lecteur dans une relation (quelquefois aride) de type professeur→étudiant ; au contraire, j'essaie de réduire la distance auteur-lecteur au minimum (au point même d'envisager la possibilité d'une certaine empathie réciproque).

La décomposition en éléments propres dans d'autres travaux

Comme déjà indiqué, il suffit de regarder comment d'autres introductions au domaine abordent la décomposition en éléments propres pour voir qu'ils ciblent un public assez différent.

Les introductions de différentes « Handbook of SDP ... » sont plutôt courtes (pas plus d'une vingtaine de pages) et elles rappellent diverses résultats avec des références vers d'autres livres pour obtenir les preuves. Ainsi, dans le « Handbook of Semidefinite Programming Theory, Algorithms, and Applications » par H. Wolkowicz, R. Saigal et L. Vandenberghe, la décomposition en éléments propres (appelée «spectral theorem») est présentée/rappelée sans preuve dans le chapitre 2. L'introduction du "Handbook on Semidefinite, Conic and Polynomial Optimization" par M. Anjost et J.B. Lasserre renvoie le lecteur au livre "Matrix analysis" par Horn and Johnson pour cette même décomposition.

Dans la thèse de HDR « Semidefinite Programming for Combinatorial Optimization », par C. Helmberg, la décomposition est présentée en annexe et redirige le lecteur vers le même livre "Matrix analysis" par Horn et Johnson. Le livre « Convex Optimization» par S. Boyd et L. Vandenberghe utilise des matrices SDP dès le début (e.g., pour définir des ellipsoïdes dans la Section 2.2.2) sans présenter le concept de matrice SDP, même pas en annexe.

J'ai aussi parcouru divers cours de master/PhD, mais certains cours ne sont pas « selfcontained » au sens fort, prenant des fois comme pré-requis certains résultats que j'ai préféré prouver dans mon manuscrit. Les slides du cours "Programmation linéaire et optimisation combinatoire" de F. Roupin pour le Master Parisien de Recherche Opérationnelle (MPRO) fournit de nombreux résultats que j'ai intégré dans mon manuscrit, mais j'ai souvent eu besoin de fournir les preuves moi-même. Le cours « Introduction to Semidefinite Programming » by R. Freund à MIT ne donne même pas la définition d'une matrice SDP avant de commencer.

Finalement, mon exposé oral va donner une ou deux preuves de cette décomposition en éléments propres, car, je répète, elle est essentielle pour comprendre les bases de l'optimisation SDP. En suivant ces preuves, les auditeurs pourraient comprendre assez vite s'ils sont attirés par ce domaine ou pas.


Daniel Porumbel
email: daniel.porumbel@cnam.fr

Sur un « détail »d'implémentation : quelques idées pour accélerer l'exécution et la programmation C++ pour la RO

Introduction

La vitesse d'exécution de tout algorithme pratique dépend d'un facteur constant de complexité δ étroitement lié à la qualité de l'implémentation. Je présente des communications à la Roadef depuis dix ans et je viens seulement de réaliser que tous mes exposés se terminent invariablement avec une phrase comme « Et pour finir, je vais vous épargner les détails d'implémentation parce que je préfère me focaliser sur l'essentiel et sur les concepts de haut niveau ». Malgré ses mérites, cette phrase est trop simpliste. Elle est de nature à éloigner le lecteur d'attention moyenne de certaines vérités. Comme une porte dérobée dans un logiciel, une conséquence inavouée est la suivante : le cout en temps de calcul est très peu impacté par (le facteur constant de complexité associé à) la qualité de l'implémentation et on peut l'ignorer. Ce facteur constant δ est aussi invisible lorsqu'on calcule des complexités théoriques comme O(n²), O(n² log n), etc. Mais imaginer un vendeur qui dit que le coût à payer est de 1000€ multiplié par un facteur constant δ=2 ou δ=6 qui n'a aucune importance dans l'absolu. N'en déplaise à certains, je ne me laisserais pas convaincre si facilement. S'il y a 15 ans on pouvait relativiser le facteur constant de complexité δ persuadés que la fréquence d'horloge des CPUs ne cessera jamais d'augmenter exponentiellement, cette idée a été un mirage en partie alimenté par une interprétation superficielle de la loi de Moore. Bien que le nombre de transistors dans un CPU peut en effet doubler tous les 18 mois, la fréquence d'horloge tend à stagner depuis 2004 et certaines limites physiques ont été atteintes. Même si j'ai aussi écrit des articles sans implémentation uniquement avec des preuves/calculs de complexités (e.g., dans la théorie des fonctions sousmodulaires), je ne veux relativiser ni le facteur constant de complexité ni le temps de programmation nécessaire pour implémenter n'importe quelle méthode pratique. Si une méthode est géniale en théorie mais trop difficile à implémenter, elle n'aura pas beaucoup de succès (penser à la méthode de l'ellipsoïde).

Bien que la théorie propose beaucoup de leviers pour déterminer le temps de calcul, la pratique est trop complexe et échappe facilement aux simplifications et axiomatisations de la théorie. Le nombre de facteurs qui rentrent en jeux est incalculable. J'ai l'habitude d'indiquer dans mes articles des facteurs comme : le langage de programmation (C++), la fréquence d'horloge, la RAM et le système d'exploitation. On comprend aisément que j'ai l'habitude de passer sous silence beaucoup d'autres aspects, comme la hiérarchie des mémoires cache, les optimisations des compilateurs, l'implémentation des structures de données, la vitesse du bus système qui gère l'accès du CPU à la mémoire, la qualité du matériel, etc. -cette liste pourrait s'allonger à perte de vue.

Il me paraît impossible de prendre en compte tous ces aspects et toutes leurs interactions pour déterminer le facteur constant δ. Il y a un seul fait qui peut simplifier la vie d'un programmeur en RO: on n'a pas forcement besoin d'artifices avancés de programmation en RO; les fonctionnalités d'un langage assez minimaliste comme le C sont suffisantes, au moins pour écrire des prototypes. La programmation en RO n'a pas forcement besoin de concepts ésotériques de programmation, comme sémantique dénotationnelle, dispatch multiple, manipulations de continuations, méthodes fabriques, polymorphisme, autoboxing, relations complexes de typage ou d'héritage, des classes amies,etc.

Cependant, je peux rappeler que la programmation orientée objet a été inventée par des chercheurs en RO qui avaient besoin de beaucoup d'organisation dans leur code. Cela à conduit au langage Simula qui a largement influencé Stroustrup pour concevoir le C++. On ne peut pas dire que la RO ne peut jamais avoir d'influence positive sur l'informatique, ou qu'il serait inutile de s'intéresser aux idées/pratiques qui permettraient d'alléger le fardeau des programmeurs en RO.

Quelques Pratiques de Programmation

Mon but est de parler de plusieurs pratiques de programmation que j'ai utilisées en C++. Voici un premier principe: la performance est une priorité en optimisation et il faut écrire un code aussi transparent que possible, c.à.d., il faut savoir précisément ce qui se passe quand un bloc de code est exécuté. Je ne vais pas essayer de donner des conseils de bonne conduite en programmation. Le concepteur du C++ a résolu cette question sans équivoque: «C++ is deliberately designed to support a variety of styles rather than a would-be "one true way"». En plus, j'assume le fait que j'ai un style C++ assez atypique. En fait, je suis une preuve vivante du fait que Linus Torvalds a (presque) eu raison en disant « the only way to do good, efficient, and system-level and portable C++ ends up to limit yourself to all the things that are basically available in C. » Grâce aux pratiques ci-dessus (http://cedric.cnam.fr/~porumbed/CODE_GUIDELINES) j'ai pu implémenter des algorithmes d'optimisation à une vitesse relativement satisfaisante. Par exemple, mon deuxième papier proposé à cette édition de la ROADEF est basé sur un code d'environ 14000 lignes et la programmation a pris environ un tiers du temps total du travail (2-3 mois). J'ai généralement programmé moi-même la plupart des algorithmes associés aux papiers que j'ai publiés, mais le temps dédié à la programmation n'a jamais été trop important. En programmant moi-même les algorithmes, j'ai aussi bénéficié d'un avantage vieux comme le monde : la meilleure façon de découvrir tout chose c'est toujours par expérience directe et non pas par l'intermédiaire des explications données par quelqu'un d'autre -dans l'esprit de la devise de cette communication.


Daniel Porumbel
email: daniel.porumbel@cnam.fr

Du sous-problème de séparation vers le sous-problème d'intersection dans les algorithmes de plan coupants

Keywords:

Introduction : la séparation et les plans coupants

Soit un Programme Linéaire (PL) défini sur un polytope P avec un nombre exorbitant (exponentiel) de contraintes. min d x : a x ≥ b, ∀(a, b) ∈ C = min d x : x ∈ P , Pour résoudre ce type de PL, on fait souvent appel à un algorithme de plans coupants (ou Cutting-Planes) qui ajoute les contraintes une par une, à l'aide d'un sous-problème de séparation. Il existe plusieurs variantes de Cutting-Planes. Une des plus répandue considère à chaque itération un sous-ensemble de contraintes de C et résout à l'optimalité le PL réduit associé, souvent à l'aide du Simplexe. La solution optimale r de ce PL réduit représente l'entrée du sous-problème de séparation, qui cherche un plan coupant pour séparer r.

Pour quoi opter pour un sous-problème d'intersection ?

Illustrons les idées principales par un exemple simple mais bien révélateur. Supposons que r = [1 1 1] soit solution optimale à l'itération courante où l'algorithme de plans coupants doit choisir une des contraintes suivantes :

(1) (

4x 1 + 6x 2 + 8x 3 >=
') 0.2x 1 + 0.3x 2 + 0.4x 3 >= 1, c.-à.d., a 1 = [0.2 0.3 0.4] and b = 1 ; (2') 0.2x 1 + 0.4x 2 + 0.2x 3 >= 1, c.-à.d., a 2 = [0.2 0.4 0.2 1
] and b = 1. Si les contraintes avaient été écrites de cette manière dès le début, le sous problème de séparation aurait choisi (2'). On peut dire que (2') est une contrainte plus forte, plus violée par r, car (a 2 ) r < (a 1 ) r. Il est facile d'argumenter que c'est mieux de normaliser les contraintes pour pouvoir les comparer de manière non biaisée.

Le sous-problème d'intersection revient à normaliser les contraintes avant d'appeler le sous problème de séparation. Il demande de résoudre

t * = max (a,b)∈C b a r (1)
S'il doit choisir entre les contraintes (1) et (2), il choisit (2), car 20 4+6+8 = 1+ 1 9 < 1+ 1 4 = 5 1+2+1 .

Des bornes supérieures avant la fin de la convergence

Le plus souvent, un algorithme de plans coupants basé sur le sous-problème de séparation ne peut pas trouver de solution réalisable (borne supérieure) avant la fin de la convergence. Un avantage important du sous-problème d'intersection est le fait qu'il génère assez simplement une solution réalisable t * r à chaque itération. En effet, l'équation (1) ci-dessus garantit que a (t * r) ≥ b ∀(a, b) ∈ C . En effet, s'il y avait une contrainte (a ι , b ι ) ∈ C tel que a ι (t * r) < b ι , le sous problème d'intersection aurait trouvé un résultat bι a ι r > t * in (1). La figure ci-contre est révélatrice des raisons pour nommer (1) un sous-problème d'intersection. Les bornes supérieures pourraient être très utiles par exemple dans un algorithme de branch-and-bound, pour élaguer des noeuds de l'arbre de recherche.

La difficulté algorithmique du sous-problème d'intersection

Le sous-problème d'intersection demande de maximiser un ratio [START_REF] Charnes | Programming with linear fractional functionals[END_REF]. Il est assez clair que cela est sans doute plus difficile que de maximiser un objectif linéaire comme max (a,b)∈C b-a r dans le sous-problème de séparation. Cependant, il existe des cas où il est possible de résoudre le sous-problème d'intersection avec un algorithme de même complexité que l'algorithme de séparation. J'ai étudié deux contextes où le sous-problème d'intersection est aussi facile que celui de séparation : (a) la génération de colonnes [START_REF] Porumbel | Ray projection for optimizing polytopes with prohibitively many constraints in set-covering column generation[END_REF] et (b) la décomposition de Benders [START_REF] Porumbel | From the Separation to the Intersection Sub-problem in Benders Decomposition Models with Prohibitively-Many Constraints[END_REF].

Par rapport à (a), il est connu que la génération de colonnes résout un PL dual avec un nombre exponentiel de contraintes ; les deux sous-problèmes (intersection ou séparation) peuvent souvent se résoudre par programmation dynamique [START_REF] Porumbel | Ray projection for optimizing polytopes with prohibitively many constraints in set-covering column generation[END_REF]. En utilisant la programmation dynamique, le fait qu'on optimise un ratio ne complique pas la résolution, car il suffit de renvoyer l'état associé au ratio le plus élevé. Pour (b), le sous-problème de séparation demande de maximiser un PL sur un polytope de Benders. Le sous-problème d'intersection (1) demande de résoudre un Programme Linéaire-Fractionnaire (PLF) sur le même polytope de Benders. J'ai pu utiliser la transformation Charnes-Cooper [START_REF] Charnes | Programming with linear fractional functionals[END_REF] pour transformer le PLF en PL, et ainsi, l'algorithme d'intersection a la même complexité que l'algorithme de séparation. En plus, le modèle de décomposition de Benders demande souvent de minimiser un PL en Nombres Entiers (master PLNE). La résolution itérative de ce PLNE est beaucoup plus coûteuse que la résolution du sous-problème d'intersection ou séparation (qui utilise que des PLs non entiers).

  20, c.-à.d., a 1 = [4 6 8] and b 1 = 20 ; (2) x 1 + 2x 2 + x 3 >= 5, c.-à.d., a 2 = [1 2 1] and b 2 = 5. Le sous-problème de séparation standard choisirait le plus souvent (1), par exemple en résolvant max (a,b)∈C ba r. Il est cependant facile d'argumenter que la contrainte (2) est plus forte que la (1). Il suffit de normaliser les contraintes, pour obtenir des contraintes équivalentes :

FIG. 1 -

 1 FIG.1-Un appel de sousproblème d'intersection qui génère la solution réalisable 2r.

Conclusions et perspectives

La contrainte d'espace ne me permet pas de présenter des tableaux avec des résultats numériques, mais je me permets de renvoyer le lecteur vers [2,3] pour des tests expérimentaux. Le code source est disponible en ligne à cedric.cnam.fr/~porumbed/irm/ ou resp. cedric. cnam.fr/~porumbed/benders/ avec quelques exemples de tableaux de résultats.

Ces tests numériques suggèrent qu'il pourrait être bien efficace de remplacer le sous-problème de séparation par celui d'intersection, surtout lorsqu'on peut le résoudre en un temps de calcul similaire au sous-problème de séparation. Je pense que l'approche pourrait être implémentée sur encore d'autres modèles, au moins pour produire des bornes supérieures en cours de route.


Pascal Mérindol

Virginie Van Den Schrieck

Benoit Donnet

Olivier Bonaventure

Jean-Jacques Pansiot
email: pansiot@unistra.fr

Quantifying ASes Multiconnectivity Using Multicast Information

Keywords: C.2.1 [Network Architecture and Design]: Network topology network topology, mrinfo, ASes connectivity, multicast

Redundant connectivity (or multiconnectivity) between adjacent autonomous systems (ASes) is important for interdomain traffic engineering and fast recovery in case of failures. However, the redundancy of ASes business relationship links has not been quantitatively studied, mainly due to the difficulty of obtaining relevant data. In this paper, we show that the mrinfo multicast monitoring tool can provide useful data about the Internet topology and such redundant links in particular. Our analysis relies on more than four years of daily queries to about ten thousand routers mapped into more than two hundred ASes. We demonstrate that peering links between ASes are frequently redundant. In particular, our analysis shows that more than half of the studied ASes pairs are connected through multiple physical links. We then refine our analysis by considering the different types of ASes and their business relationships. A particular result of our analysis is that at least 75% of the peer-to-peer relationships between adjacent Tier-1 ASes are redundant, i.e., the connections between these ASes involve several physical links. Our analysis is conservative, providing so a lower bound, as some links might not be seen by mrinfo due to ISPs filtering policies.

INTRODUCTION

Today's Internet is composed of more than 30,000 administratively independent entities called Autonomous Systems (ASes). Many researchers have developed techniques to discover its topology [START_REF] Donnet | Internet topology discovery: a survey[END_REF][START_REF] Haddadi | Network topologies: Inference, modeling and generation[END_REF] at two different levels: the router level, describing how routers are interconnected, and the AS level, defining the logical interconnection between ASes. While the router level graph is mostly built using traceroute (see Donnet and Friedman for a survey [START_REF] Donnet | Internet topology discovery: a survey[END_REF]), the AS level graph is typically constructed through BGP dumps (see references cited by Haddadi et al. [START_REF] Haddadi | Network topologies: Inference, modeling and generation[END_REF]).

In the AS level graph, two ASes are interconnected with a single logical link, hiding the potential multiple physical links between their routers. With this AS level graph, we thus lose information on how each pair of ASes is connected. Note that ISPs peering agreements often include requirements for establishing physical disjoint links [START_REF] Feamster | Borderguard: Detecting cold potatoes from peers[END_REF].

Such a redundancy of interdomain links is of the highest importance. Indeed, interdomain links fail [START_REF] Bonaventure | Achieving sub-50 milliseconds recovery upon bgp peering link failures[END_REF] and it is important to recover from these failures. Solutions have been proposed to recover from such failures locally [START_REF] Bonaventure | Achieving sub-50 milliseconds recovery upon bgp peering link failures[END_REF] or by using an alternate AS-level path [START_REF] Kushman | R-BGP: Staying connected in a connected world[END_REF][START_REF] Liao | Reliable interdomain routing through multiple complementary routing processes[END_REF]. Furthermore, several researchers have proposed different techniques to exploit such redundant links [START_REF] He | Toward Internet-wide multipath routing[END_REF][START_REF] Wischik | The resource pooling principle[END_REF][START_REF] Xu | MIRO: Multi-path interdomain routing[END_REF]. However, up to now and to the best of our knowledge, this redundancy has not been studied in details. This is mainly due to the difficulty in obtaining a data set relevant for that purpose. Indeed, standard ways of collecting topological information, such as traceroute and BGP dumps, are known to be inaccurate [START_REF] Oliveira | In search of the elusive ground truth: The Internet's AS-level connectivity structure[END_REF][START_REF] Zhang | How DNS misnaming distorts internet topology mapping[END_REF][START_REF] Teixeira | In search of path diversity in ISP networks[END_REF].

In this paper, based on a large and unexploited dataset obtained with the mrinfo [START_REF] Jacobson | mrinfo[END_REF][START_REF] Pansiot | mrinfo dataset[END_REF] IP multicast tool, we tackle the problem of quantifying the multiconnectivity of ASes. By multiconnectivity, we mean the redundancy between neighbor ASes. Note that ASes multiconnectivity is different from multihoming [START_REF] Agarwal | OPCA: Robust interdomain policy routing and traffic control[END_REF], where a stub AS is connected to several providers.

Our quantification is based on a four year daily dataset collected by mrinfo [START_REF] Pansiot | mrinfo dataset[END_REF], a tool that silently discovers all interfaces belonging to an IPv4 multicast enabled router and the IP addresses of its neighbors. In contrast to traceroutelike probing, the major advantage of mrinfo is to capture links that are not used in the normal forwarding plane such as backup links. Indeed, even if a link has a high IGP weight or a low BGP local preference, mrinfo is able to capture it. Further, mrinfo is able to discover all interfaces on a router, avoiding so the risk of missing links or approximations during the alias resolution. Our analysis demonstrates that more than half of the studied ASes pairs are connected through multiple physical links. In addition to this general analysis, we provide a classification of multiconnectivity that is based on the classical AS hierarchy (Tier-1, Transit, Stub) and AS business relationships (peer-to-peer, customer-to-provider, providerto-customer). Among others, we show that roughly 75% of the peer-to-peer relationships between adjacent Tier-1 ASes are composed of multiple links. The results of our evaluation should allow for more accurate topology generation, by providing router-level information on the interconnections between ASes.

The remainder of this paper is organized as follows: Sec. 2 discusses the mrinfo tool and the dataset we collected; Sec. 3 analyzes the ASes multiconnectivity; Sec. 4 positions this paper regarding the state of the art; finally, Sec. 5 concludes this paper by summarizing its main contributions and discussing future directions.

MRINFO

In the late 1980s, the developers of IP Multicast designed the MBone, an overlay network composed of tunnels that interconnected workstations running an implementation of the Distance Vector Multicast Routing Protocol [START_REF] Pusateri | Distance vector multicast routing protocol version 3 (DVMRP)[END_REF] (DVMRP). Several tools have been developed to monitor and debug the MBone [START_REF] Sharma | IP multicast operational network management: Design, challenges, and experiences[END_REF]. Most of these tools have been deprecated with the replacement of DVMRP by the Protocol Independent Multicast (PIM) family of multicast routing protocols with one notable exception : mrinfo [START_REF] Jacobson | mrinfo[END_REF].

mrinfo uses the Internet Group Management Protocol (IGMP) [START_REF] Deering | Host extensions for IP multicasting[END_REF]. IGMP was designed to allow hosts to report their active multicast groups to a multicast router on their LAN. Most IGMP messages are sent with a Time-to-Live of 1. However, DVMRP has defined two special types of IGMP messages that can be used to monitor routers [START_REF] Pusateri | Distance vector multicast routing protocol version 3 (DVMRP)[END_REF]. Although current IPv4 multicast routers do not use DVMRP anymore, they still support these special IGMP messages. Upon reception of an IGMP ASK NEIGHBORS message, an IPv4 multicast router will reply by sending an IGMP NEIGH-BORS reply message that provides the list of all its local interfaces with some information about their state. Cisco and Juniper routers also report in the IGMP NEIGHBORS message the version of their operating system. Fig. 1 shows an example of the usage of mrinfo to query the router R2 (1.1.0.2 is the responding interface of R2). mrinfo reports that this router is directly connected to R0 (through the in-terface 1.1.0.1) and to two AS border routers (ASBRs) R3 (through the interface 2.2.4.2) and R4 (through the interface 2.2.1.2). This information is obtained by sending a single IGMP message. In practice, mrinfo provides similar information as a show command on the router's command line interface.

Compared to traceroute and its variants, mrinfo has both drawbacks and advantages. The main drawback of mrinfo is that it can only be used on routers having IPv4 multicast activated. IPv4 multicast is not always enabled in IP networks, but thanks to the deployment of video or television services that rely on IP multicast, more and more ISP networks have enabled multicast. IGMP, like ICMP which is used by traceroute, can be disabled or rate limited on routers. More and more operators filter or rate limit ICMP, but fortunately for our measurements not all of them are aware of this special usage of IGMP.

The main advantage of mrinfo is that, in a single IGMP reply, a router lists all its interfaces, their IP addresses, and the IP addresses of its neighbor routers. Thus, mrinfo does not suffer from the alias resolution problems affecting traceroute. Second, all links of a responding router are captured, even if the IGP weight of a link is high and no data packet are forwarded over it. Furthermore, the IGMP monitoring load is very small compared to traceroute. Indeed, with mrinfo it is possible to collect the topology of a multicast enabled network by sending a single packet to each router.

Standard traceroute is only able to discover a single path from the source to the destination. To discover more topology information, it is required to increase both the number of destinations and vantage points. However, standard systems that extensively trace the Internet, such as the recent Archipelago [START_REF] Hyun | Internet mapping: from art to science[END_REF], mostly rely on a small set of sources (roughly 20 machines spread around the world). Paris Traceroute [START_REF] Augustin | Avoiding traceroute anomalies with paris traceroute[END_REF] is able to discover load balancing routers, as well as the set of paths joining those load balancing routers. However, this works mostly for intra-domain routers, BGP load balancing being much more difficult to detect. mrinfo is able to discover all links between routers from a single source if domains authorize multicast. In particular, mrinfo is able to report backup links inside and between domains. Intradomain backup links are links configured with a high IGP weight. They are not used to forward data packets and thus cannot be discovered by traceroute. Interdomain backup links can be configured by using different types of BGP policies. A frequent policy is to attach a low BGP localpreference attribute to the routes learned from a backup link. For instance, on Fig. 1, if the link between R2 and R3 has a low local preference, it will never be discovered by traceroute-like exploration but mrinfo will report it.

Dataset and Collection Methodology

Since May 1 st , 2004, we collect the mrinfo data from a host located at the University of Strasbourg, France. In this paper, we consider the data collected until October 31 st , 2008. The entire dataset is publicly available [START_REF] Pansiot | mrinfo dataset[END_REF]. The collection script maintains a list of known multicast routers. Each day, it sends an IGMP query to each of these routers to collect their list of interfaces. If a new router is discovered in a received answer (in the list of outgoing interfaces of an already known router), this router is also queried in turn. For instance, in Fig. 1, when R2 replies to mrinfo, in the next iteration of our collection script, an IGMP query will be sent to R0, R4, and R3. These recursive queries stop at unresponsive routers or when all known routers have been queried. Each router is queried at most once per day. It is worth to notice that a router not replying to an mrinfo probe during a given day will not be queried the days after except if it appears again in a list of captured interfaces. Additional information about the collection script and the raw mrinfo dataset may be found in [START_REF] Pansiot | Local and dynamic analysis of Internet multicast router topology[END_REF].

Fig. 2 provides some information on data captured by mrinfo during the four years of collection. In particular, Fig. 2(a) provides the number of routers replying to mrinfo during the four years of the data gathering, while Fig. 2(b) provides the number of IP interfaces listed by mrinfo on these routers every day. We see that the best period for mrinfo was between 2006 and 2007. On average, mrinfo was able to daily discover roughly 10,000 different routers while scanning 100,000 interfaces, and 1,000 ASBRs belonging to 200 ASes (not shown in Fig. 2). In particular, we collect data about six Tier-1 ASes such as Sprint, UUnet, and Level3. For instance, during the whole period analyzed, we received responses from, on average, 684 routers belonging to the Sprint network. Note that for Fig. 2(b) and the remainder of this paper, we remove interfaces with non publicly routable IP addresses. The addresses of those interfaces are a subset of the special-use IPv4 addresses described in RFC 3330 [START_REF] Iana | Special-use IPv4 addresses[END_REF]. Specifically, we eliminate the private IP address blocks 10.0.0.0/8, 172.16.0.0/12, and 192.168.0.0/16. We also remove the loopback address block 127.0.0.0/8 and the 0.0.0.0 address. On average, 25% of the interfaces collected by mrinfo fall within this category. We also remove all multicast tunnel interfaces to focus on actual physical links.

AS MULTICONNECTIVITY ANALYSIS

In this section, we quantify the ASes multiconnectivity based on the mrinfo dataset. We first explain the methodology we follow throughout this quantification (Sec. 3.1). We next provide a broad and general view of the ASes multiconnectivity (Sec. 3.2). We then deepen our analysis by evaluating the impact of peering relationships on ASes multiconnectivity (Sec. 3.3).

Methodology

We first merge the daily traces in weekly traces to cope with the fact that some routers might have been missed on a given day but unlikely during an entire week. Each weekly trace contains the interfaces of routers that replied at least once during the week. Since the number of routers responding with a different list of interfaces during a week is not significant, we also merge the list of captured interfaces of each router during a week. 1 For information, less than 1% of the interfaces collected by mrinfo during a given week correspond to new interfaces appearing in previously known routers. Among the four years of data, we select 100 weekly traces uniformly distributed on the whole mrinfo data set. With this subset of weekly traces, as mentioned later in Sec. 3.2, we achieve a sufficient accuracy for the purpose of our study.

Second, we map each IP address with the corresponding AS based on a longest prefix matching. This mapping is done by using a BGP table from the corresponding week obtained from Routeviews (the collector located in Oregon). We remove from weekly data traces the IP addresses that could not be mapped (less than 1% of the IP addresses collected) as well as those advertised by multiple ASes (less than 0.3% of the addresses fell in this category). We identify a responsive router as an ASBR if its outgoing interfaces are mapped to several ASes or if there exists another replying router (belonging to a neighbor AS) connected to it through one or several of its interfaces. It is worth to notice that the prefix assigned to a link connecting two ASBRs from different ASes is taken from the address space of one of the ASes. In order to affect an AS number to a given ASBR, we use a simple election process. We select the AS with the maximum number of mapped interfaces. However, in less than 0.5% of the cases (i.e., equality case), we arbitrarily select the first AS by lexicographical order. Developing smarter algorithms for assigning AS number to ASBR is subject to further work.

In addition, based on Caida data [START_REF] Caida | AS relationships[END_REF], we assign a level to each AS: Tier-1, Stub and Transit. An AS is identified as a Tier-1 if it does not maintain any customer-to-provider relationship. Similarly, an AS is labeled as Stub if it does not have any provider-to-customer relationship. With the Caida AS ranking data set [START_REF] Caida | AS relationships[END_REF], we then label business relationships: customer-to-provider (c2p), provider-to-customer (p2c), peer-to-peer (p2p), and siblings (s2s). In contrast to Routeviews data, the Caida data set is not refreshed daily. For instance, between 2004 and 2005, it was only monthly refreshed, whereas since 2006, it is weekly refreshed. Therefore, we decide to use the data which is chronologically the closest to the BGP table provided by Routeviews. 2Note that the two mapping phases (the IP to AS and the business relationships) act as a filter to suppress from our analysis the connections between ASes that do not correspond to actual BGP peering sessions. Indeed, when an Internet Exchange Point (IXP) is captured by mrinfo queries, it will find the IP addresses of all routers attached to the IXP. Although present on the IXP, all these routers do not necessarily peer which each other. To avoid over-estimating the multiconnectivity in this case, we decide to eliminate ASes connections that do not appear in BGP table dumps. This filtering may also eliminate actual BGP peering sessions as a false negative but ensures that results presented In the following of the paper, we present multiconnectivity results as cumulative distribution function (CDF) plots. Instead of evaluating the multiconnectivity evolution over time, we plot the proportion of ASes pairs that are multiconnected (i.e, the ASes pairs are connected with, at least, two physical links) as CDF. On each plot, the horizontal axis gives the proportion of multiconnected ASes pairs while the vertical axis gives the CDF. Note that in the following we analyze ASes pairs multiconnectivity as directed connections, such that each directed connection between neighbor ASes is considered independently.

Overall Analysis

Fig. 3 provides a global overview of the ASes multiconnectivity. In particular, Fig. 3(a) quantifies the ASes pairs multiconnectivity. We notice that, for 90% of the processed weeks, more than 50% of the ASes pairs captured with mrinfo present a redundant connectivity (see the dashed lines). In more than 80% of the cases, between 50% and 56% of the ASes pairs are redundant. On average, we measure that 54% of ASes pairs present a redundant connectivity. This result is based on the 100 weeks we processed with a confidence interval of 0.04% using a confidence level of 95%.

Generally speaking, Fig. 3(a) emphasizes the high degree of multiconnectivity between ASes pairs. This result is a lower bound on the actual redundancy. mrinfo might miss some inter-AS connections but cannot introduce nonexisting ones. This limitation is partially due to some ISPs packet filtering policies and the fact that some routers are not multicast native even if they belong to ASes providing multicast capabilities. Moreover, we observed that this result is not time dependent (not shown in this paper) and reflects the operators goal of being strongly connected.

Fig. 3(b) quantifies the number of physical links involved in the connectivity redundancy. This result is plotted on the week during which the largest number of routers responded to mrinfo. First, we notice that, obviously, the general result presented in Fig 3(a) is consistent with Fig 3(b). Indeed, in more than 50% of the cases, ASes pairs are connected through at least two physical links. We also notice that the number of involved physical links is not really high: 40% of ASes pairs being multiconnected have a degree of connectivity greater or equal to three physical links.

In the following, we refine this analysis to consider a taxonomy highlighting the different kinds of redundancy. In particular, we choose to differentiate multiple AS connec-

Level (# AS) Relationship (# AS

Impact of Policies

In Sec. 3.2, we saw that, on average, 54% of the ASes pairs are composed of multiple connections. In this section, we look closer at the ASes multiconnectivity. We propose a taxonomy based on two categories. The first one, labeled multiple routers (mr ), describes a situation in which two ASes are connected through multiple links and through multiple routers. This category has the advantage of protecting an AS against router and link failures. The second one, labeled single router (sr ), illustrates situations in which the pair of ASes is connected through multiple links, but with a single router on each side. This comes with the drawback of protecting only against link failures. If mrinfo captures a connection in both directions (i.e., it detects ASBRs involved in this connection in the two neighbor ASes), we label this connection as mr if, at least, one of the two ASes has several ASBRs ensuring the multiconnectivity of the relationship. If there exists several links from an ASx to several addresses belonging to an ASy, but these addresses are not responding to mrinfo, then they are counted for only one router (sr ), since they could belong to multiple interfaces of the same router. Note, however, that it might be possible that ASy provides several routers. This, actually, might lead to an overestimation of the actual sr redundancy compared to the mr redundancy. sr redundancy (parallel links) may be motivated by throughput gain.

In this section, we study the distribution of the multiconnectivity based on this taxonomy and on a hierarchical basis, i.e., for Tier-1, Transit, and Stub ASes. For all ASes in a given hierarchy level, we consider the business relationships, as discussed in Sec. 3.1. Note that we assume the s2s relationship as being a particular case of p2p, then we aggregate both into p2p. 3Table 1 shows the number of ASes falling into each level, as well as the number of business relationships identified in each level. Note that each number in the table is the mean over the 100 weeks processed (in small font, we also provide the 95% confidence interval around the mean). Obviously, all possible business relationships are not valid at all levels. For instance, a c2p relationship is prohibited at the Tier-1 level. Such a prohibited relationship is denoted ∅. 4 The column labeled "?" indicates the number of relationships that we were not able to map using Caida data. It is worth to notice that we discarded such unmapped relationships from our analysis. This implies that several relationships are not considered to ensure that the connectivity results presented here correspond to actual BGP peering sessions.

First, we should emphasize a bias in Table 1 due to two reasons. First, the mrinfo AS probing vision is not necessarily symmetric. For instance, let us assume that a link between ASx and ASy has been captured by mrinfo through an outgoing interface of an ASBR belonging to ASx. If ASy has not enabled IPv4 multicast, it will not reply to mrinfo queries, leading to a link discovered from ASx to ASy but not from ASy to ASx. Second, since our router-to-AS election mechanism (see Sec. 3.1) is somewhat naive, we only consider ASBRs whose outgoing interfaces are mapped to several ASes. Furthermore, c2p relationships are more represented than p2c because, generally, the AS provider gives IPs from its address space to its customers. Those reasons lead to the asymmetry observed in Table 3.1 between p2c and c2p relationships.

Thus, in our analysis, c2p relationship of Transit ASes is the most represented category. We notice that our mrinfo dataset captures, on average, more than 200 ASes and more than 500 connections between them.

Fig. 4 to Fig. 6 plot the CDF of the multiconnectivity proportion as explained in Sec. 3.1. On all those figures, according to our classification, we plot two curves: the first one, labeled mr shows the fraction of multiconnectivity involving multiple routers, while the second one, labeled "total", provides the proportion of multiconnected relationships whatever its label (mr or sr ). These results must be read in parallel with Table 1. To interpret this set of figures, it is necessary to consider the gap between the two curves in order to determine the proportion of multiconnected relationships not involving multiple routers (sr ).

Fig. 4 shows the Tier-1 ASes multiconnectivity. The mean of the multiconnected Tier-1 pairs proportion is within the range [0.6; 0.9] (Fig. 4(a)). The vast majority (roughly 75%) of p2p relationship between Tier-1 ASes are redundant, particularly through the mr way (roughly 70%). We however observe that p2c relationships (Fig. 4(b)) are less protected in general, approximatively 65% of these relationships are multiconnected. These p2c relationships involve fewer routers than the p2p ones (roughly 55% belongs to the mr category). Compared to ASes mapped to lower level of hierarchy, the Tier-1 ASes are much more multiconnected between themselves and with their customers than the other categories, as discussed below in this section.

Transit ASes (Fig. 5) seem to be less multiconnected than Tier-1 ASes. On average, the multiconnected Transit ASes proportion is larger than 50%. Fig. 5 shows that p2p and c2p relationships are more redundant than p2c relationships. This might be explained by the mrinfo bias discussed earlier in this section. Note that the set of p2c relationships belonging to Transit ASes is the lowest multiconnected category in all the analysis, partially because, in this study, we do not consider ASBRs whose all outgoing interfaces are mapped to the same AS. Moreover, it is worth to notice that the lower multiconnectivity fraction of p2c relationships in Fig. 5(c) is probably due to our underestimation of p2c relationships. Consequently, it might appear that multiconnectivity is not significantly different for Transit and Stub ASes. Finally, the sr and the mr redundancy seem to be well balanced whatever the category of relationships analyzed.

For the Stub ASes, we present the c2p relationships (on average, only five p2p/s2s relationships of Stub ASes are captured). Stub ASes (Fig. 6) seem to be more multiconnected than Transit ASes. Globally, 60% of the c2p relationships for Stub ASes are redundant, and as with Transit ASes, it is well balanced between mr and sr.

The classification and taxonomy results presented in this section allow us to conclude that Tier-1 ASes often achieve a high degree of redundancy involving several ASBRs to establish relationships between them as well as with their customers. Transit and Stub ASes results indicate that the multiconnectivity seems to be a less important requirement for ASes which are not in the top of the AS level graph hierarchy. In particular, the measured redundancy for intermediate and leaf ASes involves fewer ASBRs than with Tier-1 indicating that the level of protection achieved seems to be lower.

RELATED WORK

During the past decade, a large amount of efforts have been done for mapping the Internet topology, mostly using traceroute-like exploration [START_REF] Donnet | Internet topology discovery: a survey[END_REF]. However, traceroute is unable to capture links that are not currently used to forward packets, such as backup links. On the contrary, mrinfo is able to discover all the links between routers, even those having a high IGP weight or a low BGP local preference. Note that Paris Traceroute [START_REF] Augustin | Avoiding traceroute anomalies with paris traceroute[END_REF] is able to detect load-balancing routers and, by extension, multiple paths between a source and a destination [START_REF] Augustin | Measuring load-balanced paths in the Internet[END_REF][START_REF] Veitch | Failure control in multipath route tracing[END_REF]. But this is done by injecting a large quantity of packets in the network. Other extensions to traceroute use the IP Record Route option to improve topology discovery, mostly for the alias resolution [START_REF] Sherwood | Touring the internet in a TCP sidecar[END_REF][START_REF] Sherwood | DisCarte: a disjunctive Internet cartographer[END_REF]. But this does not fix the issue of revealing non-active links.

Magnien et al. recently showed the emergence of new IP addresses during repeated traceroute explorations [START_REF] Magnien | Fast dynamics in Internet topology: Preliminary observations and explanations[END_REF]. However, they do not quantify multiple paths between ASes, neither propose a classification.

Teixeira et al. evaluate the IP-level path diversity between Points of Presence (PoPs) [START_REF] Teixeira | In search of path diversity in ISP networks[END_REF]. Using the real Sprint ISP show that all pairs of PoPs have, at least, two disjoint paths between them. However, based on active measurement techniques, they notice that the resulting topologies over-estimate the path diversity between PoPs within an ISP. They suspect that the large number of false links is due to imperfect alias resolution. Nevertheless, this could not explain the false PoP level edges. Recent developments by Pai et al. [START_REF] Zhang | How DNS misnaming distorts internet topology mapping[END_REF] show that DNS misnaming appears to be a major source of false edges and offer ways to fix them.

CONCLUSION

To the best of our knowledge, prior to this paper, there did not exist accurate measurements analyzing the ASes multiconnectivity. Indeed, existing tools such as traceroute do not allow to correctly measure the degree of connectivity redundancy between ASes pairs. To avoid this drawback, we use the IPv4 multicast tool mrinfo whose main specificity is to capture all interfaces attached to replying routers. Therefore, we are also able to capture backup links that are not discovered by traceroute probing.

In this paper, using a consistent data set based on more than four years of mrinfo traces, we quantify the multiconnectivity between neighbor ASes. As a general result, we demonstrate that, on average, more than half of the ASes pairs are connected by, at least, two inter-domain links. In addition, we propose a taxonomy of the multiconnectivity and classify each relationship according to an accurate AS level hierarchy.

As further work, we will investigate other advantages provided by mrinfo exploration. In particular, we are interested in the alias resolution issue and the possibility to provide better topology model for both intra-and inter-domain levels.

Figure 1 :

 1 Figure 1: mrinfo output

Figure 2 :

 2 Figure 2: Data captured by mrinfo over time

Figure 3 :

 3 Figure 3: Multiconnectivity

Figure 4 :

 4 Figure 4: Tier-1

Figure 5 : Transit Figure 6 :

 56 Figure 5: Transit Figure 6: Stub (c2p)

Table 1 :

 1 Taxonomy general view tions involving several routers from those implying only physical links between two routers, each one being in one of the two ASes. Indeed, for fast recovery mechanisms such as those proposed by Bonaventure et al.[START_REF] Bonaventure | Achieving sub-50 milliseconds recovery upon bgp peering link failures[END_REF], the protection level (preventing from links or routers failures) depends on the multiconnectivity nature. In the next section we introduce a taxonomy allowing to consider this distinction. For instance, during the first week of February 2006, our mrinfo queries have captured that Sprint and Level3 are connected through five routers and eight physical links in the direction Sprint→Level3.

						pairs) Total
			p2p	c2p	p2c	?
	Tier-1	6±0 16±1	∅	15±1	7 ±1	38
	Transit 129±4 35±2 126±8 97±4 135 ±7	393
	Stub	93±3	5±0	80±3	∅	39 ±2	124
	Total	228	56	206	112	155	555

We assume that there are fewer router configuration changes during a week than the number of routers and interfaces not captured by mrinfo during a day.

[START_REF] Haddadi | Network topologies: Inference, modeling and generation[END_REF] We assume that business relationships do not change sufficiently frequently to introduce a significant bias in our analysis.

s2s relationships are not significantly represented in our dataset, less than 0.01% of captured connections fall in this category.

Note that our classification results are consistent with this observation.

Acknowledgements

This work has been partially supported by the Europeanfounded 216372 Trilogy project. Mr. Donnet's work is supported by the FNRS (Fonds National de la Recherche Scientifique, rue d'Egmont 5 -1000 Bruxelles, Belgium.).

Authors would like to thank anonymous reviewers, Cristel Pelsser, Steve Uhlig, and Jennifer Rexford for their helpful comments on the paper.


ICUBE Jean-Philippe Abegg Transchain

Publish/subscribe is a communication paradigm used in distributed applications to easily exchange messages. This paradigm usually has a centralized architecture where a broker is responsible for transferring all the messages, hence can be a source of trust issues. In a threat model where the broker can be malicious, two honest entities cannot be sure of the origin of a message. There exist propositions for distributed publish/subscribe protocols replacing the broker by a blockchain. Those propositions all have in common an extensive usage of the blockchain, which makes them expensive over time, due to blockchain fees, and not scalable.

In this paper, we introduce SUPRA, a distributed publish/subscribe protocol. This protocol has the same security guarantees than other solutions relying on blockchains, but where the vast majority of messages are off-chain. The message exchanges are done mostly directly between publishers and subscribers and the blockchain is only used in case of network issues, if a message is lost, or an entity is suspected to be malicious. blockchain, publish/subscribe protocol, missing messages detection, MQTT

Introduction

Publish/subscribe model is a paradigm for communication protocols. This communication model is more scalable and resource-efficient than the request-reply model [START_REF] Th Eugster | The many faces of publish/subscribe[END_REF]. There are different kinds of publish/subscribe protocols and we will focus on topic-based publish/subscribe protocols [START_REF] Th Eugster | The many faces of publish/subscribe[END_REF]. In such protocols, subscribers declare their interest in data, associated with a given topic, from a publisher, by sending a subscription. Then, when the publisher generates new data with this topic, it sends it to its subscribers. This paradigm allows a unidirectional message flow from the publisher to its subscribers.

These lightweight protocols are well suited for Internet of Things (IoT) applications but have a major drawback: the central entity in the system, the broker. In most existing protocols, such as MQTT, the publisher never sends directly the messages to its subscribers, but to the broker, which forwards the data to the subscribers. The subscribers also send their requests to the broker and not directly to the publishers. This third party between the publisher and the subscribers can create trust issues. This lack of trust makes most of the existing publish/subscribe protocols unable to be used for sensitive data.

In this context, cryptography can help to create verifiable communications and blockchain can be used as a trusted third-party between unknown entities to resolve conflicts.

Related works

Trinity [START_REF] Gowri Sankar Ramachandran | Trinity: A distributed publish/subscribe broker with blockchain-based immutability[END_REF][START_REF] Gowri Sankar Ramachandran | Trinity: A byzantine fault-tolerant distributed publishsubscribe system with immutable blockchain-based persistence[END_REF] is to our knowledge the first proposition for a publish/subscribe protocol that relies on a blockchain to work. In this solution, brokers use the blockchain to replicate data and store them in an immutable way. When a client publishes data by sending it to its broker, the broker forwards it to a blockchain node. The data eventually appears in a block so that other brokers retrieve this information by reading the blockchain and forward the published data to their local subscribers.

This interaction between a publish/subscribe protocol and a blockchain creates a secured system where we can trust the brokers because each received data can be linked to the entity that published it. However, this approach does not scale for two reasons. First, writing on the blockchain is not free. Each new transaction/data has a cost (transaction fees). With this price, the network can stay alive by paying blockchain nodes for their work. Over time, if a lot of data are published, this kind of solution could become expensive for the brokers or the clients.

Second, data in the blockchain is immutable, so each newly published data increases the size of the blockchain. The more data is sent on the blockchain, the more storage is needed for nodes. It is based on these two reasons that we design a distributed publish/subscribe protocol that uses as few blockchain transactions as possible.

After Trinity, other variants were presented [START_REF] Lv | An IOT-oriented privacy-preserving publish/subscribe model over blockchains[END_REF], but keeping this extensive use of blockchain for each newly published data.

2 General concepts of SUPRA

Managers and workers

The publish/subscribe model is composed of three entities: the broker, the publisher, and the subscriber. They create a star-topology where the broker is in the center. As long as the broker is owned by a third party, there is a trust issue with the broker.

In the manager/worker model, there are two kinds of entities: the workers and the managers. The workers generate data, spontaneously, like a sensor, or with an input from another worker, like a server with a request. This input dependency can be translated into topics used by the publish/subscribe protocol. Each worker is connected to a manager and can only send messages to its manager. The manager is in charge of the good behavior of a set of workers, and it handles the security policies in place between it and its workers. The manager is also connected to other managers. The model does not impose properties on the link between the worker and the manager, nor specific protocols on this link. We assume that each worker has total trust in its manager. This assumption is easily achievable if the worker and the manager are owned by the same entity.

Managers can be publishers and subscribers at the same time. The managers do not trust each other and to share data, they will use the hybrid channel presented in the next section.

Unidirectional Channel with On-Off Chain Proof of Delivery

We present now a new communication protocol, used by SUPRA, but can be of independent interest. The purpose of this protocol is to allow one manager to send messages to another one, with delivery guarantees, and such that each manager obtains proofs for each of those guarantees. The communication protocol is a unidirectional channel, but the goal is similar to the bidirectional channels defined in the Lightning network [START_REF] Poon | The bitcoin lightning network: Scalable off-chain instant payments[END_REF]. We suppose that the managers are reliably connected to the same blockchain.

The publisher manager sends its messages to the subscriber manager using two methods, as illustrated by Figure 1. With the first method, the messages are sent like any other messages on the internet, directly to the subscriber manager, using its IP address, such messages are said to be sent off-chain because the blockchain is not used by this method. The receiver has to acknowledge this message. With the second method, the messages are sent on the blockchain, included in a block, and the subscriber manager indirectly receives the message by reading the blockchain. In this case, the messages are said to be sent on-chain. With these two methods, the sender is sure that the messages are delivered before a timeout T , because the message is either explicitly acknowledge, or acknowledge by assumption because the managers are connected to the blockchain.

Also, just like the blocks in a blockchain, messages are chained together with signatures. It allows the receiver to detect if messages are missing.

SUPRA

SUPRA is a publish/subscribe protocol between managers using the unidirectional channel with on-off chain proof of delivery. A more complete presentation of the protocol can be found in our technical report [START_REF] Abegg | Supra, a distributed publish/subscribe protocol with blockchain as a conflict resolver[END_REF].

Users use the blockchain to declare public keys, and these keys are used to sign the messages. The hybrid channel is set up with a triple handshake between the publisher and the subscriber, where they share the topic name. Once it is set up, the publisher can send data to the subscriber. The publisher is sure that the subscriber will receive the data, because of the proofs of delivery generated with the channel. Since messages are chained together and signed, the subscriber is sure that it has not missed a message, and that the messages are from the publisher.

Comparison with existing solutions

SUPRA and Trinity are two publish/subscribe protocols using the blockchain. They resolve the issue with the central broker. Firstly because the message is signed by the sender. Secondly, because missing messages can be detected. Trinity does it by sending all the messages on-chain, and SUPRA by chaining the message together. The major difference between these two protocols is on the blockchain usage. With SUPRA, published data go through the blockchain only if there is a connectivity issue with the off-chain link. It reduces the amount of messages on-chain, and so the cost of the communications because there are less transaction fees. It also impact the delivery delay. Indeed, the off-chain link is faster than the on-chain link because we do not have to wait for the message to be added in a block. The channel makes in general SUPRA deliver data faster than Trinity. In the worst-case scenario, when the off-chain link is lost, SUPRA has the same delay as Trinity, because just like Trinity, every message will go through the blockchain.

Conclusion

The blockchain technology can be used to increase the security of the publish/subscribe paradigm. Existing solutions overuse the blockchain, which makes than expensive overtimes. We propose a new technique to use the blockchain to reduce drastically the number of messages on-chain, while keeping the same security properties.

Figure 1 :

 1 Figure 1: The two modes of communication of our unidirectional on/off chain channel protocol