Brevet FR3093878A1 — publié le 20200918

Description Titre de l'invention : Procédé et dispositif d'estimation de dis- tributions probabilistes d'une métrique additive Domaine technique de l'invention [0001] La présente invention concerne de manière générale le domaine technique de de la surveillance des réseaux informatiques. [0002] Elle concerne en particulier un procédé et un dispositif d'estimation de distributions probabilistes d'une métrique additive. Etat de la technique [0003] Il a déjà été proposé d'estimer les distributions probabilistes d'une métrique additive respectivement associées à des liens d'un réseau à partir de valeurs de bout-en-bout de cette métrique, mesurées pour des chemins formés par des liens du réseau. [0004] Une telle métrique additive est par exemple un retard de transmission des données dans le réseau ou (après transformation logarithmique) un taux de perte de paquets de données au sein du réseau. [0005] L'article "Network delay tomography using flexicast experiinents", de E. Lawrence, G. Michailidis et V. N. Nair, in J. R. Statist. Soc B (2006), 68, partie 5, pp. 785-813 propose dans ce cadre d'estimer les distributions probabilistes au moyen d'un algorithme espérance-maximisation. [0006] La solution proposée dans cet article est toutefois liée à la topologie arborescente du réseau et n'est donc pas applicable à des réseaux ayant une configuration différente. Présentation de l'invention [0007] Dans ce contexte l'invention propose un procédé d'estimation de distributions proba- bilistes d'une métrique additive respectivement associées à des liens d'un réseau, comprenant une pluralité d'itérations comprenant chacune des étapes de : [0008] - production d'une pluralité de vecteurs tests conformément à une distribution de pro- babilité courante indiquant pour chaque lien une répartition probabiliste parmi différentes valeurs de la métrique additive pour ce lien, les composantes de chaque vecteur test correspondant à des valeurs potentielles de la métrique additive respectivement associées auxdits liens, [0009] - sélection des vecteurs tests pour lesquels une valeur représentative de la distance entre un ensemble de valeurs de bout-en-bout, calculées en fonction des composantes du vecteur test concerné, et un ensemble de valeurs de bout-en-bout mesurées est inférieure à un seuil ; [0010] - détermination de la nouvelle distribution de probabilité courante sur la base des vecteurs tests sélectionnés ; 2 [0011] le procédé comprenant en outre au moins une étape de diminution du seuil entre deux desdites itérations. [0012] La distribution de probabilité courante converge ainsi vers les distributions proba- bilistes recherchées, ce au moyen d'opérations relativement simples et peu coûteuses en mémoire. [0013] D'autres caractéristiques non limitatives et avantageuses du produit/procédé conforme à l'invention, prises individuellement ou selon toutes les combinaisons techniquement possibles, sont les suivantes : [0014] - l'étape de sélection utilise une matrice A indiquant, pour chacun d'une pluralité de chemins, les liens utilisés par le chemin concerné ; [0015] - chaque ligne de la matrice A est associée à un chemin de ladite pluralité de chemins ; [0016] - chaque colonne de la matrice A étant associée à un lien du réseau ; [0017] - un élément d'une colonne donnée et d'une ligne donnée de la matrice A est nul si le chemin associé à la ligne donnée ne comprend pas le lien associé à la colonne donnée, et/ou non-nul (par exemple égal à 1) si le chemin associé à la ligne donnée comprend le lien associé à la colonne donnée ; [0018] - les composantes d'un vecteur Y valent respectivement, pour ladite pluralité de chemins, les valeurs de bout-en-bout mesurées pour le chemin concerné ; [0019] - ladite distance vaut IA.X - YI pour un vecteur test X ; [0020] - les vecteurs tests sélectionnés à l'étape de sélection sont les vecteurs tests X qui vérifient IAX-YI / (U.B) 100), ici T = 5000. [0114] Par exemple, pour chaque vecteur test X,, on détermine pour chaque lien L, la valeur X,[j] relative au lien Li en obtenant une valeur discrète k comprise entre 1 et D par tirage aléatoire conformément à la distribution probabiliste courante pour le lien Lj (représentée par la ligne j de la matrice a) et en affectant la valeur (bk_I-Ebk)/2 à l'élément concerné du vecteur test X, (X,[j] = (1'1+1')/2). [0115] Les composantes de chaque vecteur test X, correspondent ainsi à des valeurs po- tentielles de la métrique additive respectivement associées aux liens U. Ces valeurs possibles sont par ailleurs affectées aux composantes des différents vecteurs tests X, de la pluralité de sorte qu'en considérant l'ensemble des vecteurs tests X, de la pluralité, on retrouve les distributions probabilistes courantes a[j,m] définies dans la matrice a_ [0116] Le procédé peut alors se poursuivre à l'étape El 4 par la sélection des vecteurs tests X , pour lesquels une valeur représentative de la distance IA.X, - YI est inférieure au seuil E. [0117] Les vecteurs tests sélectionnés à l'étape El4 sont donc les vecteurs tests X, pour lesquels une valeur représentative de la distance entre un ensemble de valeurs de bouten-bout, calculées en fonction des composantes du vecteur test X concerné, et l'ensemble de valeurs de bout-en-bout mesurées (contenues dans le vecteur Y) est inférieure au seuil E. [0118] En effet, comme expliqué plus haut, la matrice A représente la topologie du réseau et le produit A.X, (un vecteur de dimension N, noté Y, ci-dessous) représente donc les valeurs de bout-en-bout respectivement obtenues pour les différents chemins considérés lorsque les valeurs de la métrique additive pour les liens Li du réseau sont celles définies par le vecteur test X,. [0119] On utilise ici en tant que valeur représentative de la distance IA.X, - YI une distance moyenne normalisée ô définie comme suit (en notant Y,,A.X) : [0120] [Math.3] âtiir Y)= 1; 7 i(lYt[i] - / (U.B) [0121] où B =1)1,-boest l'écart maximal entre deux valeurs possibles de la métrique additive et U est le nombre de valeurs non-nulles dans la matrice A, autrement dit ici : [0122] 12 [Math.4] U :SLI AR, ji = 1 j = 1 [0123] Du fait de sa définition, la distance moyenne normalisée ô est toujours comprise entre 0 et 1. [0124] Les vecteurs tests X sélectionnés sont donc ici ceux qui vérifient : [0125] Ô(A.X' Y) R comme indiqué ci-dessus) comprend les opérations suivantes : [0140] - mémorisation du seuil a au sein d'une variable a2 ; [0141] - multiplication du seuils par le coefficient 13 (et mémorisation du résultat en tant que nouveau seuil a), ce qui permet de diminuer le seuil F. (car on a toujours ri 0,999), la 14 valeur du seuil E ne pourra plus diminuer significativement lors d'éventuels passages à l'étape E22 et on considère donc que le procédé d'estimation est achevé. [0152] On utilise alors à l'étape E30 les distributions probabilistes définies dans la matrice courante comme distributions probabilistes estimées par le procédé : pour chaque lien Li, la probabilité estimée d'observer une valeur de la métrique additive comprise entre b',_, et b,' est égale à la valeur de l'élément a[j,m] de la matrice courante a.. [0153] La figure 6 présente les étapes principales d'un autre exemple envisageable pour le procédé d'estimation des grandeurs descriptives de la métrique additive de l'étape E6. [0154] Cc procédé débute par une étape E50 de regroupement des chemins en groupes de chemins au sein desquels les deux chemins de chaque paire de chemins ont au moins un lien Li en commun. [0155] Grâce à un tel regroupement, les chemins d'un groupe de chemins donné impliquent seulement un sous-ensemble desdits liens Li excluant au moins un desdits liens Li (et en général une pluralité desdits liens Li). [0156] Dans l'exemple de la figure 3 par exemple, on forme à l'étape E50 deux groupes de chemins : [0157] - un premier groupe G1 comprenant les chemins Cl et C2, et impliquant donc les liens L3, L5, L6, L7, L8 (le premier groupe G1 excluant donc les liens Ll, L2 et L4) ; [0158] - un second groupe G2 comprenant les chemins C3 et C4, et impliquant donc les liens Ll, L2, L3, L4, L5 (le second groupe G2 excluant donc les liens L6, L7, L8. [0159] Pour ce faire, le processeur (ici le processeur de l'infrastructure de réseau G) applique par exemple un algorithme de partitionnement ("clustering algorithm" selon l'appellation anglo-saxonne) aux différentes lignes de la matrice A (qui sont comme déjà indiqué respectivement associées aux différents chemins à regouper) en utilisant une notion de distance prédéfinie entre deux lignes de la matrice A. [0160] Selon une possibilité de réalisation, la distance d(i,i') entre deux lignes i et de la matrice A est définie comme suit : [0161] [Math.5] d(i, r) lAri, Jl - A[i', j] = , où KI est la valeur absolue de x. [0162] L'algorithme de partitionnement permet de définir une partition de l'ensemble des lignes dc la matrice A (et donc des chemins correspondants) de sorte que chaque ensemble dc la partition forme un groupe de lignes (et donc de chemins) au sein duquel la distance d(i,i') entre deux lignes i et i' est réduite. [0163] L'algorithme de partitionnement utilisé est par exemple en pratique un algorithme des k-moyennes (ou "k-tneans algorithm" selon l'appellation anglo-saxonne). [0164] Lc procédé comprend alors une étape E52 dc détermination des grandeurs des- criptives sur la base des valeurs de bout-en-bout mesurées yi, yn, y; et en effectuant, pour un groupe de chemins Gl, G2 donné, des opérations relatives au groupe de chemins G 1, G2 donné et impliquant des valeurs de la métrique additive relatives seulement à des liens du sous-ensemble associé au groupe de chemins 01, G2 donné (à l'exclusion de valeurs de la métrique additive relatives à des liens L, non inclus dans le sous-ensemble associé au groupe de chemins donné). [0165] On décrit ci-dessous deux exemples possibles de mise en oeuvre de cette étape E52. [0166] La figure 7 présente un premier exemple envisageable pour la mise en oeuvre de l'étape E52. [0167] Dans ce premier exemple, le processeur (ici le processeur du gestionnaire d'infrastructure de réseau G) met en oeuvre, pour chaque groupe de chemins Gl, G2, une étape E54 de recherche de multiplets de valeurs de la métrique additive relatives respectivement aux liens L du sous-ensemble associé au groupe de chemins Gl, G2 et adaptées à produire, par combinaison additive, les valeurs de bout-en-bout mesurées y, , y2, yi pour les chemins du groupe de chemins Gl, G2. [0168] Dans le cas de la figure 3 par exemple et pour le groupe de chemins Gl, on recherche à l'étape E54 des multiplets (xl, xs., x6, x7, xs) tels que : [0169] - x; + xs. + x6 -F = y et [0170] - x; + x7 + Xg = y2, [0171] les valeurs x3, x5., x6, x7, xs étant des valeurs de la métrique additive respectivement associées au liens L3, L5, L6, L7, L8 et les valeurs y, et y2 étant les valeurs de bouten-bout mesurées respectivement pour les chemins Cl et C2. [0172] Pour un groupe de chemins Gl, G2 donné, ces opérations sont ainsi relatives à ce groupe de chemins et impliquent seulement des valeurs de la métrique additive relatives aux liens Li du sous-ensemble associé à ce groupe de chemins (à l'exclusion de valeurs de la métrique additive relatives à des liens Li non inclus dans ce sous-ensemble). [0173] La mise en oeuvre de la recherche de l'étape E54 groupe de chemins par groupe de chemins (plutôt que simultanément pour tous les chemins) réduit de manière importante le coût calculatoire de la recherche. [0174] La recherche de l'étape E54 est par exemple réalisée au moyen d'un résolveur récursif (ou "recursive solver" selon l'appellation anglo-saxonne). [0175] On propose ici d'utiliser un algorithme qui parcourt l'espace des solutions (multiplets permettant d'obtenir les valeurs yi mesurées dans le groupe de chemins concernés) de manière optimale afin de trouver les solutions possibles. L'espace des solutions est construit comme une arborescence dans laquelle chaque noeud représente une variable. Les différentes branches qui s'étendent à partir de chaque noeud représentent les différentes valeurs que la variable peut prendre. 16 [0176] L'algorithme proposé tente de répartir les valeurs de bout-en-bout (valeurs mesurées y, et y, dans l'exemple ci-dessus) entres les différentes variables associées aux différents liens à l'aide d'appels récursifs. [0177] Chaque appel récursif a deux paramètres : l'indice de la variable et le reste sur chaque chemin. [0178] Avant chaque appel récursif, la valeur prise par la variable est lue pour tous les chemins qui utilisent ce lien. Si le reste sur un chemin est strictement inférieur à la valeur, cette valeur ne peut pas faire partie d'une solution et l'algorithme n'effectue donc pas l'appel récursif concerné. On évite ainsi d'explorer des régions de l'arborescence des solutions qui ne correspondent pas à des solutions possibles. [0179] Lorsque l'appel récursif atteint le noeud de plus bas niveau de l'arborescence, l'algorithme vérifie que le reste sur tous les chemins est nul. Si c'est le cas, le chemin emprunté par les appels récursifs successifs correspond à une solution et est donc sauvegardé en tant que tel. [0180] On propose alors de déterminer les grandeurs descriptives (ici les distributions proba- bilistes définies au sein de la matrice a introduite plus haut) sur la base des multiplets obtenus l'étape E54 et au moyen d'un algorithme d'espérance-maximisation décrit à présent (étapes E56 et E58). [0181] Le processeur (ici le processeur du gestionnaire d'infrastructure de réseau G) procède tout d'abord à l'étape E56 à l'initialisation de la matrice a, par exemple au moyen de valeurs aléatoires. [0182] Par exemple, comme expliqué ci-dessus dans le cadre du mode de réalisation de la figure 5, on peut initialiser une matrice temporaire a' avec (pour chacun des éléments alj,m]) des valeurs aléatoires comprises entre 0 et 1. Puis on initialise la matrice a comme suit : [0183] [Math.6] OtP, = O e p, /'WU Pi P =1 [0184] Le processeur met alors en oeuvre une étape E58 dite "espérance" (ou "expectaction step" selon l'appellation anglo-saxonne) au cours de laquelle on détermine les éléments M[j,m] d'une matrice M (chaque élément représentant l'estimation du nombre d'observations de valeurs comprises entre ban et b', sur le lien TH associé à la colonne j parmi tous les multiplets obtenus à l'étape E54 pour les groupes de chemin utilisant le lien L;), par exemple comme suit : [0185] [Math.7] MM, 1111 = p tri) to ( Y ) 0.(9)Prn