H - Electricity – 04 – L
Patent
H - Electricity
04
L
H04L 12/56 (2006.01) G06F 17/30 (2006.01)
Patent
CA 2484446
Methods and apparatus are disclosed for generating and using an enhanced tree bitmap data structure in determining a longest prefix match, such as in a router, packet switching system. One implementation organizes the tree bitmap to minimize the number of internal nodes that must be accessed during a lookup operation. A pointer is included in each of the trie or search nodes to the best match so far entry in the leaf or results array which allows direct access to this result without having to parse a corresponding internal node. Moreover, one implementation stores the internal node for a particular level as a first element in its child array. Additionally, one implementation uses a general purpose lookup engine that can traverse multiple tree bitmaps or other data structures simultaneously, and perform complete searches, partial searches, and resume partial searches such as after receiving additional data on which to search.
L'invention concerne des procédés et appareils permettant de générer et d'utiliser une meilleure structure de données mode point arborescent lors de la détermination de l'adaptation de longs préfixes, comme dans un router, un système de commutation par paquets. Une application organise le mode point arborescent pour réduire au minimum le nombre de noeuds internes auquel on doit pouvoir avoir accès lors d'une opération de consultation. Un indicateur est inclus dans chaque noeud de tri ou de recherche pour une meilleure adaptation dans la mesure où l'entrée dans la feuille ou l'ensemble de résultats donne accès direct à ce résultat sans devoir analyser un noeud interne correspondant. En plus, une application stocke le noeud interne d'un niveau particulier sous forme de premier élément de son réseau enfant. Une application utilise un moteur de consultation polyvalent qui peut traverser simultanément de multiples modes points arborescents ou autres structures, et réaliser des recherches complètes, des recherches partielles et réunir des recherches partielles comme après réception de données additionnelles sur lesquelles porte la recherche.
Eatherton William
Rangarajan Vijay
Sagi Dalit
Cisco Technology Inc.
Gowling Lafleur Henderson Llp
LandOfFree
Longest prefix matching using tree bitmap data structures does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Longest prefix matching using tree bitmap data structures, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Longest prefix matching using tree bitmap data structures will most certainly appreciate the feedback.
Profile ID: LFCA-PAI-O-1836533