Re: [FRnOG] [TECH] lookup dans la FIB d'un routeur logiciel
Le 13/11/2019 à 22:09, Jérôme Marteaux a écrit : > Qu'en pensez-vous, est-ce que 24 Mo peut stocker 1 millions de route > IPv4 (sous forme d'arbre, pas > juste 1 000 000 x 4 octets !) avec les index des interfaces et les MAC > des nexthop ? > Quelle est la taille minimale nécessaire ? 4 octets pour deux index, ça fait 65536 nexthop différents. Si tu prends 3 octets pour deux index, ça fait 1024 nexthop. Et 2 : 256 nexthop. Après un peer, ça ne peut être que 1 index qui contient l'interface et la mac donc: 4 octets : 4G nexthop 3 : 16M nexthop 2 : 65536 nexthop 1 : 256 nexthop Dans ce cas, 2 octets devrait couvrir les besoins de la majorité. Au total, 2o * 1 000 000 + 65536 * ( 2o "interface", 6o "mac" ) = 2.5Mo Si on rajoute des compteurs, 2*8 octets pour chaque nexthop + 8o autre (32o au total) = 4Mo Avec 256o par nexthop = 19Mo : il y a déjà de quoi faire. Avec 3 octets : 137Mo 4 : 34Go Dans les deux derniers cas, c'est la table des interfaces/mac qui bouffe. Un hash passerait peut-être mieux --- Liste de diffusion du FRnOG http://www.frnog.org/
RE: [FRnOG] [TECH] lookup dans la FIB d'un routeur logiciel
> Benoît Ganne a écrit : > Je n'ai jamais vu d'accès DDR en moins de 100 cycles CPU... Et encore ça > c'est quand ta DDR n'est pas trop > chargée. Ca peut rapidement monter à plusieurs centaines de cycles dès que tu > commences à avoir du trafic. > Un exemple mesuré sur les serveurs du lab CSIT : > https://docs.fd.io/csit/master/report/vpp_performance_tests/test_environment.html#id5 > => on voit que la latence de la DDR va de ~80ns (~200 cycles @2.5GHz) en idle > à ~280ns (~700 cycles @2.5GHz) quand elle est chargée. Ah la vache c'est bien pire que ce que je pensais, merci pour le lien. Bah, encore une idée à jeter. J'ai appris quelque chose, merci. Michel. --- Liste de diffusion du FRnOG http://www.frnog.org/
Re: [FRnOG] [TECH] lookup dans la FIB d'un routeur logiciel
Le 13/11/2019 à 20:00, Michel Py a écrit : >> Radu-Adrian Feurdean a écrit : >> 3) la mise a jour : imagine deja la mise a jour d'un /16 (65K entrees a >> mettre a jour), ou encore pire d'un /10 :) > Certes, mais à comparer avec ce que çà fait gagner, 85 cycles d'horloge à > chaque paquet. > Comparativement à plusieurs millions de paquets par seconde, la mise à jour > est très rare. > > En plus, la DDR c'est lent sur des accès individuels, mais pas pour les gros > blocks. DDR4 récente c'est au moins 40 GO par seconde en écriture. > Un /10 avec 8 Octets par IP çà représente 32 MO de mémoire, moins de 1ms en > théorie. Il doit bien y avoir des instructions pour gérer çà en DMA ou autres > sans même avoir une boucle bourrin. > > Michel. > Je partage un graphique, ce sont des chiffres intéressants sur les différentes grandeurs qui ont cours aujourd'hui: http://i.imgur.com/k0t1e.png (même la RAM coûte cher en perf, et c'est pas le média le plus lent !). Ecrire dans la RAM va vite sur un bloc contigu de mémoire. Si ce n'est pas contigu, ça se transforme vite en des accès aléatoire (patricia est orienté lecture plutôt qu'être optimisé délai pour mettre à jour l'arbre). L'autre problème qui me semble important c'est qu'il y a plusieurs consommateurs (les core qui routent) et un core qui va mettre à jour la RAM, il faut donc un système qui permet de verrouiller la mémoire le temps de la mise à jour. Ces systèmes là sont lents. Mais les routes ne sont pas les seuls éléments à stocker, il y a aussi de la config, des compteurs, des interfaces, des adresses MAC, des neighbors IPv6, des pointeurs... Si avant chaque accès il faut demander l'usage exclusif de la ressource, les perfs s'écroulent. Est-ce qu'il ne faudrait pas alors avoir n copie de la FIB (et de tous les autres éléments) avec n le nombre de core ? (et en archi NUMA). Il me semble que c'est le principe de DPDK, affecter des core à une fonction unique et précise. Et qu'il soit capable de faire ce job le plus indépendamment possible, en évitant de faire du context switching. Globalement il faut se passer un maximum de la RAM, utiliser un maximum le cache (qui aujourd'hui est énorme, on peut en stocker des infos dans 24 Mo. Et même bientôt 128 Mo). Qu'en pensez-vous, est-ce que 24 Mo peut stocker 1 millions de route IPv4 (sous forme d'arbre, pas juste 1 000 000 x 4 octets !) avec les index des interfaces et les MAC des nexthop ? Quelle est la taille minimale nécessaire ? A cela il faut rajouter les problèmes de pipeline (mauvaises prédictions) ... et c'est l'enfer. Jérôme -- Jérôme Marteaux --- Liste de diffusion du FRnOG http://www.frnog.org/
Re: [FRnOG] [TECH] lookup dans la FIB d'un routeur logiciel
>>> Michel Py a écrit : >>> Est-ce que çà ne vaudrait pas le coup de gaspiller 32GO de DDR4 pour >>> réduire ces 35ns >>> à 1 accès mémoire ? >> 1) d'abord ça va te coûter plus que 32Go : il faut stocker les infos >> nécessaires au routage : interface de sortie, etc. Ca prend plusieurs octets > Combien ? avec 32 GO, j'avais prévu au pif 8 octets : 4 pour > l'adresse de la passerelle, 2 pour l'interface de sortie, et 2 je > sais pas trop pourquoi. Je ne sais pas précisément, mais déjà tu vas sans doutes vouloir gérer de l'ECMP maintenir des statistiques... >> 2) avec un espace pareil, tous tes lookups vont misser en cache, tu va >> partir en DDR à chaque fois. Avec un trie, on bénéficie du fait que >> l'adressage réseau est hiérarchique pour pouvoir mieux cacher les entrées > C'est pas évident, car çà dépend du nombre de flux actifs. C'est à > prévoir, mais combien de ns çà prend un accès en DDR ? d'après ce que > je comprends, c'est environ 10ns a CAS19, ce qui ferait quand même > gagner 25ns par lookup. Je n'ai jamais vu d'accès DDR en moins de 100 cycles CPU... Et encore ça c'est quand ta DDR n'est pas trop chargée. Ca peut rapidement monter à plusieurs centaines de cycles dès que tu commences à avoir du trafic. Un exemple mesuré sur les serveurs du lab CSIT : https://docs.fd.io/csit/master/report/vpp_performance_tests/test_environment.html#id5 => on voit que la latence de la DDR va de ~80ns (~200 cycles @2.5GHz) en idle à ~280ns (~700 cycles @2.5GHz) quand elle est chargée. ben --- Liste de diffusion du FRnOG http://www.frnog.org/
RE: [FRnOG] [TECH] lookup dans la FIB d'un routeur logiciel
>> Michel Py a écrit : >> Est-ce que çà ne vaudrait pas le coup de gaspiller 32GO de DDR4 pour réduire >> ces 35ns >> à 1 accès mémoire ? D'après ce que dit Ben le lookup çà serait a peu près la >> moitié >> de la performance, donc on pourrait en théorie doubler la performance d'un >> routeur soft. > Benoît Ganne a écrit : > Je ne crois pas que ce soit aussi simple : le soucis avec du direct > addressing, > c'est que : 1) d'abord ça va te coûter plus que 32Go : il faut stocker les > infos > nécessaires au routage : interface de sortie, etc. Ca prend plusieurs octets Combien ? avec 32 GO, j'avais prévu au pif 8 octets : 4 pour l'adresse de la passerelle, 2 pour l'interface de sortie, et 2 je sais pas trop pourquoi. > 2) avec un espace pareil, tous tes lookups vont misser en cache, tu va > partir en DDR à chaque fois. Avec un trie, on bénéficie du fait que > l'adressage réseau est hiérarchique pour pouvoir mieux cacher les entrées C'est pas évident, car çà dépend du nombre de flux actifs. C'est à prévoir, mais combien de ns çà prend un accès en DDR ? d'après ce que je comprends, c'est environ 10ns a CAS19, ce qui ferait quand même gagner 25ns par lookup. C'est bourrin comme méthode, mais 25ns par paquet ce n'est pas rien. Michel. --- Liste de diffusion du FRnOG http://www.frnog.org/
RE: [FRnOG] [TECH] lookup dans la FIB d'un routeur logiciel
> Radu-Adrian Feurdean a écrit : > 3) la mise a jour : imagine deja la mise a jour d'un /16 (65K entrees a > mettre a jour), ou encore pire d'un /10 :) Certes, mais à comparer avec ce que çà fait gagner, 85 cycles d'horloge à chaque paquet. Comparativement à plusieurs millions de paquets par seconde, la mise à jour est très rare. En plus, la DDR c'est lent sur des accès individuels, mais pas pour les gros blocks. DDR4 récente c'est au moins 40 GO par seconde en écriture. Un /10 avec 8 Octets par IP çà représente 32 MO de mémoire, moins de 1ms en théorie. Il doit bien y avoir des instructions pour gérer çà en DMA ou autres sans même avoir une boucle bourrin. Michel. --- Liste de diffusion du FRnOG http://www.frnog.org/
Re: [FRnOG] [TECH] lookup dans la FIB d'un routeur logiciel
On Tue, Nov 12, 2019, at 20:08, Benoît Ganne wrote: > Je ne crois pas que ce soit aussi simple : le soucis avec du direct > addressing, c'est que : > 1) d'abord ça va te coûter plus que 32Go : il faut stocker les infos > nécessaires au routage : interface de sortie, etc. Ca prend plusieurs > octets, donc on parle plutôt de 100Go-1To. Ca commence à piquer :) > 2) avec un espace pareil, tous tes lookups vont misser en cache, tu va 3) la mise a jour : imagine deja la mise a jour d'un /16 (65K entrees a mettre a jour), ou encore pire d'un /10 :) --- Liste de diffusion du FRnOG http://www.frnog.org/
RE: [FRnOG] [TECH] lookup dans la FIB d'un routeur logiciel
>> Michel Py a écrit : >> Est-ce que çà ne vaudrait pas le coup de gaspiller 32GO de DDR4 pour réduire >> ces 35ns >> à 1 accès mémoire ? D'après ce que dit Ben le lookup çà serait a peu près la >> moitié >> de la performance, donc on pourrait en théorie doubler la performance d'un >> routeur soft. > Benoît Ganne a écrit : > Je ne crois pas que ce soit aussi simple : le soucis avec du direct > addressing, > c'est que : 1) d'abord ça va te coûter plus que 32Go : il faut stocker les > infos > nécessaires au routage : interface de sortie, etc. Ca prend plusieurs octets Combien ? avec 32 GO, j'avais prévu au pif 8 octets : 4 pour l'adresse de la passerelle, 2 pour l'interface de sortie, et 2 je sais pas trop pourquoi. > 2) avec un espace pareil, tous tes lookups vont misser en cache, tu va > partir en DDR à chaque fois. Avec un trie, on bénéficie du fait que > l'adressage réseau est hiérarchique pour pouvoir mieux cacher les entrées C'est pas évident, car çà dépend du nombre de flux actifs. C'est à prévoir, mais combien de ns çà prend un accès en DDR ? d'après ce que je comprends, c'est environ 10ns a CAS19, ce qui ferait quand même gagner 25ns par lookup. C'est bourrin comme méthode, mais 25ns par paquet ce n'est pas rien. Michel. --- Liste de diffusion du FRnOG http://www.frnog.org/
Re: [FRnOG] [TECH] lookup dans la FIB d'un routeur logiciel
> Est-ce que çà ne vaudrait pas le coup de gaspiller 32GO de DDR4 pour réduire > ces 35ns à 1 accès mémoire ? > D'après ce que dit Ben le lookup çà serait a peu près la moitié de la > performance, donc on pourrait en théorie doubler la performance d'un routeur > soft. Je ne crois pas que ce soit aussi simple : le soucis avec du direct addressing, c'est que : 1) d'abord ça va te coûter plus que 32Go : il faut stocker les infos nécessaires au routage : interface de sortie, etc. Ca prend plusieurs octets, donc on parle plutôt de 100Go-1To. Ca commence à piquer :) 2) avec un espace pareil, tous tes lookups vont misser en cache, tu va partir en DDR à chaque fois. Avec un trie, on bénéficie du fait que l'adressage réseau est hiérarchique pour pouvoir mieux cacher les entrées - je spécule un peu et je n'ai pas de de données pour comparer, mais par exemple si tu as 2 /16 dans ta fib, en direct addressing ce sera trop éloigné pour être caché, alors qu'avec un trie ils seront typiquement sur la même cacheline Et le lookup représente moins de 30% : il y a également la gestion de l'ECMP et des stats dedans. ben --- Liste de diffusion du FRnOG http://www.frnog.org/
RE: [FRnOG] [TECH] lookup dans la FIB d'un routeur logiciel
> Vincent Tondellier a écrit : > https://vincent.bernat.ch/fr/blog/2017-progres-ipv4-table-routage-linux Très intéressant, merci. Donc, environ 35ns. Est-ce que çà ne vaudrait pas le coup de gaspiller 32GO de DDR4 pour réduire ces 35ns à 1 accès mémoire ? D'après ce que dit Ben le lookup çà serait a peu près la moitié de la performance, donc on pourrait en théorie doubler la performance d'un routeur soft. Michel. --- Liste de diffusion du FRnOG http://www.frnog.org/
Re: [FRnOG] [TECH] lookup dans la FIB d'un routeur logiciel
Le Monday 11 November 2019 21:42:08 Michel Py a écrit : > Question pour Ben et ceux qui ont regardé le code d'un lookup de FIB : > J'ai toujours imagine que la FIB était stockée dans une espèce d'arbre > binaire ou une table de hashing. Est-ce que je me trompe ? C'est un genre d'arbre : PATRICIA tree ou radix tree Voir l'excellent article de Vincent Bernat pour l'implementation Linux : https://vincent.bernat.ch/fr/blog/2017-ipv6-table-routage-linux (et oui il y a aussi la version pour le protocole historique, le lien est dans l'intro) Voir aussi ces articles qui sont dans le sujet du thread : https://vincent.bernat.ch/fr/blog/2017-progres-ipv6-table-routage-linux https://vincent.bernat.ch/fr/blog/2017-progres-ipv4-table-routage-linux --- Liste de diffusion du FRnOG http://www.frnog.org/
RE: [FRnOG] [TECH] lookup dans la FIB d'un routeur logiciel
Question pour Ben et ceux qui ont regardé le code d'un lookup de FIB : J'ai toujours imagine que la FIB était stockée dans une espèce d'arbre binaire ou une table de hashing. Est-ce que je me trompe ? Et maintenant question encore plus bête, pourquoi est-ce qu'il n'y a pas de lookup a plat ? Une FIB avec 4 milliards d'entrées. Certes çà va bouffer 32 GO ou plus de mémoire, mais un lookup ne prendrait qu'un seul accès mémoire. Michel. --- Liste de diffusion du FRnOG http://www.frnog.org/
