# Segmentation à faible coût des délais réseau basée sur le regroupement hiérarchique

Sanaa Ghandi, Alexandre Reiffers-Masson, Sandrine Vaton, Thierry Chonavel

► To cite this version:

Sanaa Ghandi, Alexandre Reiffers-Masson, Sandrine Vaton, Thierry Chonavel. Segmentation à faible coût des délais réseau basée sur le regroupement hiérarchique. GRETSI 2023, Aug 2023, Grenoble, France. hal-04154351

HAL Id: hal-04154351

https://inria.hal.science/hal-04154351

Submitted on 6 Jul 2023

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
Segmentation à faible coût des délais réseau
basée sur le regroupement hiérarchique

Sanaa GHANDI¹ Alexandre REIFFERS-MASSON¹ Sandrine VATON¹ Thierry CHONAVEL¹

¹IMT Atlantique, Lab-STICC, UMR CNRS 6285, F-29238 Brest, France

**Résumé** – Les mesures de délai Internet sont importantes pour la supervision des réseaux. En particulier, la caractérisation des délais est utile pour la surveillance des infrastructures et l'analyse des incidents. Cet article explore l'utilisation du regroupement hiérarchique pour la segmentation multivariée des délais réseaux. Cette méthode identifie les corrélations spatiales et segmente conjointement les séries temporelles au sein d'un même groupe de délais. Une étape de lissage utilisant l'algorithme de Viterbi est proposée comme post-traitement pour mieux intégrer la dépendance temporelle. Cette méthode globale est évaluée sur un ensemble de données réelles, mettant en évidence des performances satisfaisantes et un coût de calcul limité.

**Abstract** – Internet delay is an important metric in network monitoring. In particular, delay characterization is useful for infrastructure monitoring and incident analysis. This paper explores the use of hierarchical clustering for the segmentation of multivariate network delays. This method identifies spatial correlations and jointly segments time series within the same delay cluster. A smoothing step using the Viterbi algorithm is proposed as a post-treatment to better incorporate the temporal dependence of delays. This global method is then evaluated on a real dataset, demonstrating a satisfying performance and limited computational cost.

# 1 Introduction

Le délai Internet de bout en bout (RTT) est une métrique réseau importante. En effet, elle peut être utile pour l'évaluation des performances réseau, l'état d'un chemin ou la qualité de l'expérience utilisateur. En règle générale, les mesures de délai présentent des schémas similaires lorsque les itinéraires suivis partagent des segments de chemins. Dans [9], il a été observé que les délais entre les paires passant par le même point d'échange Internet (IXP), présentaient des changements d'état synchronisés. La figure 1, permet de mettre en évidence cette corrélation spatiale. En effet, la similitude de comportement observée dans ces séries temporelles peut être attribuée au routage sous-jacent du réseau.

<figure><img src="image_2.png" /><figcaption>FIGURE 1 : Séries temporelles de délai représentant des changements synchronisés.</figcaption></figure>

Traditionnellement, la segmentation des délais a été confiée à des experts humains, comme l'illustre la figure 2, qui montre la facilité avec laquelle un individu peut effectuer cette tâche. Néanmoins, compte tenu de l'abondance des données disponibles sur des plateformes telles que Ripe Atlas et Caida, il est à la fois coûteux et difficile de s'appuyer sur des analystes

humains pour accomplir cette segmentation. Il est donc nécessaire de créer des outils et des algorithmes appropriés pour répondre à cette demande croissante.

<figure><img src="image_3.png" /><figcaption>FIGURE 2 : Une trace de délai de bout en bout observée pendant une semaine sur Ripe Atlas. La segmentation et le clustering sont indiqués par les différentes couleurs.</figcaption></figure>

De nombreux travaux [4], [15, 8] ont visé à modéliser les délais Internet dans le temps afin d'avoir une meilleure idée du fonctionnement du réseau. En outre, Shao et al. [13] ont étudié la segmentation des délais de bout en bout pour évaluer l'impact des changements de routage à différents niveaux (AS, IXP) sur les changements de délais. Par ailleurs, Mouchet et al. [9] ont utilisé la méthode HDP-HMM pour détecter les pannes de l'IXP sur la base de la fréquence des changements des délais. Finalement, la caractérisation des délais a été traitée autant par des études basées sur les distributions [15], [12], [5], que par des approches basées sur l'apprentissage profond [11].

Malgré la grande précision de la segmentation des séries de délais obtenue dans certains travaux cités, l'état de l'art présente deux problèmes principaux. Tout d'abord, ces approches sont très gourmandes en ressources informatiques. Deuxièmement, les études ne prennent en compte que la stabilité temporelle des séries temporelles, sans tirer pleinement parti des dépendances spatiales entre séries. À notre connaissance, le présent document propose la première segmentation multivariée des délais réseau avec un coût de calcul limité.

Dans cet article, nous explorons l'utilisation du regroupe-
ment hiérarchique pour la segmentation multivariée des délais réseaux. Cet algorithme est d'abord appliqué à la matrice de corrélation de Pearson des séries temporelles de délai de bout en bout pour capturer la corrélation spatiale dans l'ensemble des données. Lorsque les groupes sont identifiés, il est utilisé une seconde fois pour segmenter conjointement les séries temporelles au sein de chaque groupe. Ensuite, nous proposons une étape de post-traitement en exploitant l'algorithmme de Viterbi, qui est capable de lisser la segmentation résultante pour traiter la dépendance temporelle de manière plus efficace. Cette méthode globale est évaluée sur des données réelles, démontrant son faible coût de calcul et son aptitude à gérer des délais avec des configurations variées.

L'article est structuré comme suit. La deuxième section présente la méthodologie. Elle commence par expliquer le regroupement hiérarchique et son application pour l'identification des séries temporelles corrélées. Ensuite, elle décrit la segmentation multivariée en deux étapes basée sur le regroupement hiérarchique et le lissage par Viterbi. La troisième section évalue la méthode de segmentation en la comparant en matière de précision et de temps d'exécution à la méthode HDP-HMM. Enfin, la quatrième partie conclut ce travail et propose des pistes de recherche pour l'avenir.

# 2 Méthodologie

## 2.1 Principes du regroupement hiérarchique

Le regroupement hiérarchique est une technique de regroupement agglomératif populaire utilisée pour regrouper des variables sur la base de leur similarité. Cette approche consistera que chaque élément constitue initialement son propre groupe. Ensuite, les groupes sont fusionnés de manière itérative pour former des groupes plus grands. À chaque étape, les deux groupes les plus proches sont fusionnés en un nouveau groupe père. Ce processus est répété jusqu'à ce qu'un seul groupe global subsiste après N-1 itérations, avec N le nombre de variables [6]. Ce processus de regroupement itératif peut être représenté sous la forme d'un dendrogramme, c'est-à-dire d'une structure arborescente.

La similarité entre les groupes est mesurée à l'aide d'une méthode de couplage, telle que le couplage simple, couplage, moyenne, centroïde ou de Ward [10]. Le couplage simple prend en compte les éléments les plus proches des groupes. Le couplage complet considère les éléments les plus éloignés. Le couplage moyen considère la distance moyenne entre tous les éléments. Le couplage centroïde est basé sur la distance entre les centroïdes des groupes respectifs. Et le couplage de Ward minimise la variance des groupes fusionnés.

Dans le présent document, nous utilisons le couplage complet pour le regroupement des séries temporelles et le couplage de Ward pour la segmentation. En effet, ces deux couplages sont les seuls à pouvoir gérer le bruit et les valeurs aberrantes. Le couplage complet n'est toutefois pas adapté à la stationnarité, car il a tendance à briser les grands groupes [14].

## 2.2 Le regroupement des séries temporelles

Afin de tirer profit de la corrélation spatiale des délais, une première étape consiste à regrouper les séries temporelles de caractéristiques similaires. Pour ce faire, on utilise le modèle

hiérarchique pour un regroupement efficace. À cette fin, nous introduisons la notation suivante. Nous considérons que le temps est divisé en créneaux temporels. Et nous supposons qu'un réseau contenant *n* paires de source/destination est observé pendant une durée de *T* créneaux. Nous nous intéressons aux mesures de délai entre chaque source et destination de ces paires. La matrice *D* représente la série temporelle à *n*-variée et de longueur *T*. $D_i$: est la ligne *i* de la matrice *D* et représente la série temporelle de délais observée du *i*-ème couple source/destination et $D_{i,j}$ la colonne *j* de la matrice *D* représente le vecteur des délais mesurés pendant le créneau *j*.

Pour mettre en évidence la corrélation spatiale entre les séries temporelles, une matrice de corrélation de Pearson est calculée entre chaque paire de lignes de la matrice *D*. Un regroupement hiérarchique est ensuite effectué sur les valeurs de la matrice de corrélation. Ce regroupement est obtenu en déterminant un seuil optimal de troncature du dendrogramme. L'objectif de ce seuil est de former le nombre minimum de groupes qui maximise la corrélation des séries temporelles au sein de chaque groupe. À cette fin, nous définissons le critère suivant. Pour une partition *P* de l'ensemble de données, nous définissons la métrique : $h(P) = \sum_{c \in P} \sum_{s_k, s_l \in c} |corr(s_k, s_l)|$, avec $corr(x, y)$ la corrélation de Pearson entre les paires *x* et *y*. Afin d'effectuer notre partition, nous fixons le seuil de troncature à la valeur qui maximise ce critère.

## 2.3 Lissage de Viterbi

Nous proposons de saisir la corrélation temporelle en modélisant les délais multivariés présents dans $D^c$ pour chaque groupe *c* identifié à l'aide d'un modèle de Markov caché. Ce modèle considère que les vecteurs de délai observés ($D_i^c, i \le T$) sont générés par certains états cachés ($e_k, k \le m$. En fait, l'hypothèse markovienne des changements de délai Internet est couramment utilisée dans la littérature [9], [15].

Le problème de segmentation est reformulé comme suit : les étiquettes des segments sont définies par les états cachés et l'objectif est de les inférer sur la base des vecteurs de délai observés. À cette fin, nous utilisons un algorithme de Viterbi. C'est un algorithme de programmation dynamique permettant de trouver la séquence la plus probable d'états cachés [7] qui aboutit à la séquence d'événements observés.

Nous utilisons les résultats de la segmentation hiérarchique sur chaque matrice $D^c$ pour identifier approximativement le nombre d'états cachés et estimer la probabilité d'émission de chaque état. Le calcul des probabilités d'émission est effectué soit sur la base d'histogramme soit à l'aide d'une méthode d'estimateur de densité par noyau. De plus, nous considérons une matrice de probabilité de transition qui renforce le fait que deux délais successifs ont plus de chances d'être générés par le même état caché. Pour cette raison, nous nous plaçons dans le contexte d'une probabilité de transition qui est faible par rapport à la probabilité de rester dans le même état. Par souci de simplicité, pour un nombre *m* d'états initiaux, nous définissons la matrice de probabilité de transition $m \times m P_t$ comme suit : $P_t(i, j) = \epsilon/(m-1)$ si $i \neq j$ et $P_t(i, i) = 1-\epsilon$, avec *m* le nombre d'états cachés. Le choix d'une petite valeur de $\epsilon$ renforce la persistance des états.

Le traitement conjoint de plusieurs séries temporelles conjointement, introduit un biais lors du calcul des scores pour le chemin de Viterbi. En effet, le poids de la probabilité
de transition devient négligeable devant la probabilité d'émission quand le nombre de séries temporelles est élevé, résultant en un faible lissage. Afin de pallier ce déséquilibre, nous introduisons la régularisation suivante. Pour une segmentation de N série temporelle, la probabilité de transmission est fixée à $P_t(i, j) = (\epsilon/(m-1))^N$ si $i \neq j$ et $P_t(i, i) = (1-\epsilon)^N$. Cette version du lissage sera dénommée lissage de Viterbi régularisé.

# 3 Évaluation

## 3.1 Ensemble de données

Nous allons tester nos méthodes sur un ensemble de séries de délais issu de données du monde réel collectées à partir de Ripe Atlas, une plateforme de mesure de l'Internet. Ils représentent les délais entre les paires passant par le point d'échange DE-CIX situé à Francfort. Entre le 9 et le 20 avril 2018, le DE-CIX Francfort a connu une perturbation de sa connectivité réseau, ce qui a entraîné un reroutage et une interruption du trafic comme indiqué dans [2].

Cet ensemble de données contient 38k séries temporelles. Chacune de ces séries temporelles comporte 720 créneaux d'observation qui correspondent à deux jours de mesures.

## 3.2 Méthode de l'état de l'art

Pour ces ensembles de données, nous utilisons comme approximation de vérité terrain pour la segmentation une méthode HDP-HMM [9] qui a été validée et adaptée par Ripe Atlas dans une API [1]. Les HDP-HMM sont les modèles de Markov caché à processus Dirichlet hiérarchique. C'est un modèle bayésien non paramétrique qui permet d'inférer des données d'une complexité d'état arbitrairement grande. Il s'agit d'une extension du modèle de Markov caché qui permet de déduire le nombre d'états à partir des données, plutôt que de le spécifier a priori.

Nous allons comparer quatre variantes de la méthode proposée au HDP-HMM. D'abord, le regroupement hiérarchique seul (RH), ensuite le RH avec un seul lissage de Viterbi (V1) et le RH avec deux lissages de Viterbi (V2) et finalement le RH avec un lissage de Viterbi régularisé (V1 REG) et le RH avec deux lissages de Viterbi régularisé (V2 REG). La version V2 du lissage de Viterbi introduit une réestimation des densités d'émission à l'issue du premier lissage.

## 3.3 Métrique d'évaluation

Afin de mesurer la qualité de la segmentation, nous avons opté pour l'utilisation de l'indice de Rand ajusté. Il permet de comparer notre méthode au HDP-HMM. En effet, l'indice de Rand est une mesure de similarité entre deux partitions du même ensemble et il représente la proportion de paires de points qui sont groupées de la même façon dans les deux partitions [3]. Cet indice nous permettra de décider de la meilleure variante de la méthode à choisir.

## 3.4 Résultats

### 3.4.1 Qualité de la segmentation

La figure 3 montre l'évolution de l'indice de Rand ajusté moyen des séries temporelles d'un groupe en fonction de son cardinal pour les quatre variantes. Il est calculé entre la segmentation multivariée donnée par le groupe et la segmentation univariée donnée par le HDP-HMM pour chaque série de ce cluster.

<figure><img src="image_4.png" /><figcaption>FIGURE 3 : Rand index évalué pour les différentes méthodes par rapport au HDP-HMM.</figcaption></figure>

On peut observer que la version régularisée de Viterbi avec un seul passage affiche les meilleurs résultats. Ceci montre également l'apport de l'étape de post-traitement dans la qualité de la segmentation comparée au RH seul. On choisit donc la version régularisée avec un seul passage de Viterbi comme stratégie de segmentation.

Par ailleurs, il faut noter que l'indice de Rand ajusté moyen ne dépasse pas 0.8, ceci s'explique par plusieurs éléments. Tout d'abord, il est naturel de perdre en termes de précision vu qu'en traitant conjointement les séries de délais, il y a une dégradation par rapport à la segmentation individuelle de chaque série.

Inversement, comme peut le montrer la figure 4, sur cette segmentation, on peut observer que des phénomènes locaux touchant une seule série peuvent affecter la segmentation globale, ce qui peut induire un écart avec le HDP-HMM pour d'autres séries du groupe.

<figure><img src="image_5.png" /><figcaption>FIGURE 4 : Segmentation conjointe de 10 séries temporelles de délai représentant des changements synchronisés et un changement touchant une seule série.</figcaption></figure>
<figure><img src="image_6.png" /><figcaption>FIGURE 5 : Segmentation de deux séries temporelles appartenant au même groupe par la méthode HDP-HMM</figcaption></figure>

En outre, il faut noter que le HDP-HMM est un benchmark
utilisé actuellement, mais ne constitue pas pour autant une
vérité terrain. La figure 5 permet de voir que le HDP-HMM
a traité différemment deux séries pourtant proches. Cela peut
également contribuer à l'écart trouvé entre notre segmentation
conjointe et celle du HDP-HMM.

Globalement, la méthode permet de mettre en évidence
les schémas et les états distincts de chaque groupe de séries.
Ceci répond largement aux besoins opérationnels que peut
demander un traitement à large échelle d'un point de vue
métier.

3.4.2 Temps d'exécution

On considère maintenant le gain en termes de temps de calcul qu’apporte notre méthode comparée au HDP-HMM sur des séries de longueur 720. Le code HDP-HMM (code compilé optimisé) nécessite 2.6 secondes en moyenne pour segmenter une série temporelle, tandis que notre méthode segmente une série temporelle en 0.74 seconde en moyenne en utilisant un estimateur de densité à noyau et 0.28 secondes en utilisant des histogrammes, soit des facteurs de gain de coût de calcul respectifs de 3.5 et 9.3.

4 Conclusion

La segmentation de délais réseau est une problématique im-
portante et dans cet article, nous proposons de la résoudre
en utilisant une approche par regroupement hiérarchique suivi
d'un lissage par l'algorithme de Viterbi. Cette approche permet
de tenir compte et de la corrélation spatiale et de la corrélation
temporelle qui caractérisent les délais de bout en bout sur Inter-
net. Nous montrons sa qualité de segmentation en la comparant
au HDP-HMM et sa rapidité et performance en matière de coût
de calcul en le diminuant par un ordre de grandeur. À l'avenir,
nous explorerons la corrélation spatiale en tant que réduction
de la dimensionalité pour certains schémas de surveillance
intelligente. En outre, nous appliquerons cette méthode à un
cas d'utilisation réel tel que les incidents de points d'échange
Internet.

Références

[1] Api atlas, https://github.com/maxmouchet/atlas-trends-demo.

[2] Does the internet route around damage in 2018?, https://labs.ripe.net/author/emileaben/does-the-internet-route-around-damage-in-2018.

[3] Indice de rand, https://fr.wikipedia.org/wiki/indice_de_random.

[4] L. DAVISSON, J. JAKOVLESKI, N. NGO, C. PHAM et J. SOMMERS : Reassessing the constancy of end to end internet latency. In *IFIP Network Traffic Measurement and Analysis Conference*, 2021.

[5] José-Alberto HERNÁNDEZ et Iain W PHILLIPS : Weibull mixture model to characterise end-to-end internet delay at coarse time-scales. *IEE Proceedings-Communications*, 153(2):295-304, 2006.

[6] Xiao LIU, Xiao-Hong ZHU, Peihua QIU et Wei CHEN : A correlation-matrix-based hierarchical clustering method for functional connectivity analysis. *Journal of neuroscience methods*, 211(1):94-102, 2012.

[7] H-L LOU : Implementing the viterbi algorithm. *IEEE Signal processing magazine*, 12(5):42-52, 1995.

[8] Maxime MOUCHET, Sandrine VATON et Thierry CHONAVEL : A flexible infinite hmm model for accurate characterization and segmentation of rtt timeseries. In *IEEE INFOCOM 2019 - IEEE Conference on Computer Communications Workshops (INFOCOM WKSHPS)*, pages 1055-1056, 2019.

[9] Maxime MOUCHET, Sandrine VATON, Thierry CHONA-VEL, Emile ABEN et Jasper DEN HERTOG : Large-scale characterization and segmentation of internet path delays with infinite hmms. *IEEE Access*, 8:16771-16784, 2020.

[10] Fionn MURTAGH et Pedro CONTRERAS : Algorithms for hierarchical clustering : an overview. *Wiley Interdisciplinary Reviews : Data Mining and Knowledge Discovery*, 2(1):86-97, 2012.

[11] Daniel PERDICES, Jorge E López de VERGARA et Javier RAMOS : Deep-fda : Using functional data analysis and neural networks to characterize network services time series. *IEEE Transactions on Network and Service Management*, 18(1):986-999, 2021.

[12] Yasuhiro SATO, Shingo ATA, Ikuo OKA et Chikato FUJIWARA : Using mixed distribution for modeling end-to-end delay characteristics. In *Proceedings of the 8th Asia-Pacific Network and Management Symposium (APNOMS 2005)*, Japan, Okinawa, 2005.

[13] Wenqin SHAO, Jean-Louis ROUGIER, Antoine PARIS, François DEVIENNE et Mateusz VISTE : One-to-one matching of rtt and path changes. In *2017 29th International Teletraffic Congress (ITC 29)*, volume 1, pages 196-204. IEEE, 2017.

[14] Shweta SHARMA, Neha BATRA *et al.* : Comparative study of single linkage, complete linkage, and ward method of agglomerative clustering. In *2019 International Conference on Machine Learning, Big Data, Cloud and Parallel Computing (COMITCon)*, pages 568-573. IEEE, 2019.

[15] Wei ZHANG et Jingsha HE : Modeling end-to-end delay using pareto distribution. In *Second International Conference on Internet Monitoring and Protection (ICIMP 2007)*, pages 21-21. IEEE, 2007.