structure de données appropriée pour un tampon des paquets

Question

Comment mettre en œuvre un tampon des paquets où chaque paquet est de la forme:

typedef struct{ 
    int32 IP;  //4-byte IP-address 
    int16 ID;  //unique sequence id 
}t_Packet; 

Quelle devrait être la structure de données la plus appropriée qui:

(1) permet de collecter au moins 8000 tels paquets (opérations rapides d'insertion et de suppression)
(2) permet un filtrage très rapide en utilisant l'adresse IP, de sorte que seuls les paquets avec IP donné seront sélectionnés
(3) permet une recherche très rapide utilisant l'ID comme clé
(4) permet très rapide (2), puis (3) dans les résultats filtrés?

La taille RAM est importante, par ex. pas de grande table de recherche est possible d'utiliser.

Answer 1

Vous pouvez utiliser un Patricia Trie pour le filtrage d'adresse IP. Je crois que la plupart des routeurs de réseau utilisent cette structure de données pour les adresses IP IPv4. Il existe également d'autres essais dans la littérature conçus pour les adresses IP que vous pouvez envisager d'utiliser. En voici un: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.35.4871

En fonction de chaque adresse IP, vous pouvez désormais avoir une table de hachage basée sur l'ID. Si les adresses IP sont «suffisamment» aléatoires, il est préférable d'utiliser une hashtable pour effectuer un filtrage basé sur IP, car les adresses IP correspondent parfaitement à un mot de la plupart des machines, ce qui rend les recherches de hachage très rapides et le trie pourrait ne pas vraiment vous sauver beaucoup d'espace.

Bien sûr, le bon choix dépend de votre situation ...

Answer 2

Créer deux indices pour les données (les stocker de manière non séquentielle pour les insertions rapides, etc.), l'un par arbre divisé par ID, l'autre par arbre.

Si vous ne pouvez pas vous permettre au moins 8000 * sizeof (Packet) + 8000 * 12 + 8000 * 12 pour data + deux indices, honnêtement, iterating sur seulement 8000 articles ne prendrait pas vraiment très long.

Ce serait beaucoup plus facile à mettre en œuvre C++ que c (si seulement parce que vous pouvez utiliser boost :: multi_index, ou similaire)