Un peu d'informatique de rattrapage, pour les auditeurs PCI de mon public.
Je vous remets un tableau d'entiers aléatoires. Comment savoir si le numéro trois s'y trouve?
Eh bien, il y a la façon la plus évidente: vérifiez les chiffres de manière séquentielle jusqu'à ce que vous trouviez le «3» ou épuisez le tableau. Recherche linéaire. Étant donné 10 nombres, vous devez supposer que cela pourrait prendre 10 étapes; N nombres, N étapes.
Image 1.png
La recherche linéaire est mauvaise. Il est difficile de faire pire que linéaire. Améliorons-le. Triez le tableau.
Image 2.png
Un tableau trié suggère une stratégie différente: sautez au milieu du tableau et voyez si la valeur que vous recherchez est inférieure à (à gauche) ou supérieure à (à droite). Répétez l'opération, en coupant le tableau en deux à chaque fois, jusqu'à ce que vous trouviez la valeur.
Recherche binaire. Étant donné 10 nombres, il faudra jusqu'à 3 étapes - log2 sur 10 - pour trouver l'un d'entre eux dans un tableau trié. La recherche O (log n) est géniale. Si vous avez 65 000 éléments, il ne vous faudra que 16 étapes pour en trouver un. Doublez les éléments, et c'est 17 étapes.
Mais les tableaux triés sont nuls; d'une part, le tri est plus cher que la recherche linéaire. Nous n'utilisons donc pas beaucoup la recherche binaire; à la place, nous utilisons des arbres binaires.
Image 3.png
Pour rechercher un arbre binaire, vous commencez en haut et vous vous demandez «est ma clé inférieure (à gauche) ou supérieure à (droite) le nœud actuel», et répétez jusqu'à ce que ok, ok, ok, vous savez déjà ce genre de choses. Mais cet arbre est joli, non?
La recherche avec un arbre binaire (équilibré) est O (log n), comme la recherche binaire, variant avec le nombre d'éléments dans l'arbre. Les arbres binaires sont géniaux: vous obtenez une recherche rapide et une traversée triée, quelque chose que vous ne sortez pas d'une table de hachage. Les arbres binaires sont une meilleure implémentation de table par défaut que les tables de hachage. 2.
Mais les arbres binaires ne sont pas le seul mécanisme de recherche arborescent. Les essais de radix binaires, également appelés arbres PATRICIA, fonctionnent comme des arbres binaires avec une différence fondamentale. Au lieu de comparer plus que / moins que sur chaque nœud, vous vérifiez si un bit est défini, en vous ramifiant à droite s'il est défini et à gauche s'il ne l'est pas.
Image 4.png
Je passe beaucoup de temps sur le fonctionnement de Radix binaire. C'est dommage, car les essais radix sont notoirement sous-documentés - Sedgewick les a tristement infiltrés dans «Algorithmes», et la page Wikipedia pour eux est nul. Les gens se disputent encore sur comment les appeler! Au lieu d'une explication des backlinks et des bords étiquetés par la position des bits, voici une minuscule implémentation Ruby.
Voici pourquoi les essais radix sont cool:
Search performance varies with the key size, not the number of elements in the tree. With 16 bit keys, you’re guaranteed 16 steps
quel que soit le nombre d'éléments dans l'arbre, sans équilibrage.
More importantly, radix tries give you lexicographic matching, which is a puffed-up way of saying “search with trailing wildcard”, or
«Recherche de style de fin de ligne de commande». Dans un arbre Radix, vous pouvez rapidement rechercher «ro *» et obtenir «rome» et «romulous» et «roswell».
3.
Je t'ai perdu.
Mettons cela en contexte. Les essais sont une structure de données cruciale pour le routage Internet. Le problème de routage se présente comme suit:
You have a routing table with entries for “10.0.1.20/32 -> a” and “10.0.0.0/16 -> b”.
You need packets for 10.0.1.20 to go to “a”
You need packets for 10.0.1.21 to to to “b”
C'est un problème difficile à résoudre avec un arbre binaire de base, mais avec un trie radix, vous demandez simplement "1010.0000.0000.0000.0000.0001.0100" (pour 10.0.1.20) et "1010." (pour 10.0.0.0 ). La recherche lexicographique vous donne la «meilleure correspondance» pour le routage. Vous pouvez l'essayer dans le code Ruby ci-dessus; ajoutez * "10.0.0.0" .to_ip au trie et recherchez "10.0.0.1" .to_ip.
La correspondance entre le routage et les essais Radix est si forte que la bibliothèque de radix trie à usage général la plus populaire (celle du CPAN) est en fait volée à GateD. C'est un gâchis, d'ailleurs, et ne l'utilisez pas.
Si vous comprenez comment fonctionne un trie, vous comprenez également comment fonctionnent les expressions régulières. Les essais sont un cas particulier des automates finis déterministes (DFA), où les branches sont basées exclusivement sur des comparaisons de bits et toujours vers l'avant. Un bon moteur d'expression régulière gère simplement les DFA avec plus de «fonctionnalités». Si mes images ont du sens pour vous, les images de cet excellent article sur l'algorithme de réduction NFA-DFA de Thompson le seront également, et cet article vous rendra plus intelligent. 4.
Vous êtes un opérateur réseau chez un FAI dorsal. Votre monde se compose en grande partie de «préfixes» - des paires réseau IP / masque de réseau. Les masques de réseau dans ces préfixes sont extrêmement importants pour vous. Par exemple, 121/8 appartient à la Corée; 121.128 / 10 appartient à Korea Telecom, 121.128.10 / 24 appartient à un client KT et 121.128.10.53 est un ordinateur à l'intérieur de ce client. Si vous traquez un botnet, une opération de spam ou une propagation de ver, ce numéro de masque de réseau est très important pour vous.
Malheureusement, aussi importants soient-ils, nulle part sur un paquet IP n'est marqué un «masque de réseau» - les masques de réseau sont entièrement un détail de configuration. Ainsi, lorsque vous regardez le trafic, vous avez essentiellement ces données avec lesquelles travailler:
ips.png
Étonnamment, avec suffisamment de paquets à regarder, c'est suffisamment d'informations pour deviner les masques de réseau. Tout en travaillant chez Sony, Kenjiro Cho a trouvé une façon très élégante de le faire, basée sur des essais. Voici comment:
Prenez un trie radix binaire de base, tout comme ceux utilisés par les routeurs logiciels. Mais lié au nombre de nœuds dans l'arbre, disons à 10 000. Sur une liaison dorsale, l'enregistrement d'adresses à partir d'en-têtes IP, vous épuiserez 10 000 nœuds en quelques instants.
Stockez la liste des nœuds dans une liste, triée dans l'ordre LRU. En d'autres termes, lorsque vous associez une adresse IP à un nœud, «touchez» le nœud, en le collant en haut de la liste. Progressivement, les adresses fréquemment vues bouillonnent vers le haut, et les nœuds rarement vus coulent vers le bas.
Image 6.png
Maintenant l'astuce. Lorsque vous manquez de nœuds et avez besoin d'un nouveau, récupérez en bas de la liste. Mais quand vous le faites, faites rouler les données du nœud vers son parent, comme ceci:
Image 5.png
10.0.1.2 et 10.0.1.3 sont frères / 32 ans, les deux moitiés de 10.0.1.2/31. Pour les récupérer, fusionnez-les dans 10.0.1.2/31. Si vous devez récupérer 10.0.1.2/31, vous pouvez le fusionner avec 10.0.1.0/31 pour former 10.0.1.0/30.
Faites cela pendant, disons, une minute, et les sources exceptionnelles défendront leur position dans l'arbre en restant en haut de la liste LRU, tandis que le bruit ambiant / 32 fait des bulles jusqu'à / 0. Pour la liste brute des IP ci-dessus, avec une arborescence de 100 nœuds, vous obtenez ceci.
Cho appelle cette heuristique Aguri. 5.
Aguri est sous licence BSD. Vous pouvez aller le télécharger, et un programme de pilote qui regarde les paquets via pcap, à partir de l'ancienne page d'accueil de Cho. 6.
Je vais quelque part avec ça, mais je suis 1300 mots dans ce post maintenant, et si vous êtes une personne des algorithmes, vous en avez assez de moi maintenant, et si vous ne l'êtes pas, vous en avez assez de moi en maintenant. Alors, laissez Aguri s'enfoncer, et je vous donnerai quelque chose de cool et d'inutile à faire plus tard cette semaine.
Il existe de nombreux liens dispersés là-dedans. Malheureusement, Archive.org ne conserve pas les images, seulement le texte, donc plusieurs d'entre elles ont été perdues. Voici ceux qu'il a archivés:
