H - Electricity – 04 – L
Patent
H - Electricity
04
L
H04L 12/56 (2006.01) G06F 17/30 (2006.01)
Patent
CA 2303118
In a method of IP routing lookup in a routing table, comprising entries of arbitrary length prefixes with associated next-hop information in a next-hop table, to determine where IP datagrams are to be forwarded, a representation of the routing table is stored, in the form of a complete prefix tree (7), defined by the prefixes of all routing table entries. Further, a representation of a bit vector (8) comprising data of a cut through the prefix tree (7) at a current depth (D), and an array of pointers, comprising indices to the next-hop table and to a next-level chunk, are stored. Said bit-vector (8) is divided into bit-masks and a representation of the bit-masks is stored in a maptable. Then, an array of code words, each encoding a row index into the maptable and a pointer offset, and an array of base addresses are stored. Finally, the lookup is performed.
L'invention concerne un procédé de recherche d'acheminement Internet dans une table d'acheminement comportant des rubriques préfixes de longueur arbitraire associées à des informations Saut Suivant dans une table Saut Suivant. Ce procédé permet de déterminer où des datagrammes Internet doivent être envoyés. Une représentation de la table d'acheminement est mémorisée sous la forme d'un arbre de préfixes complet (7), défini par les préfixes de toutes les rubriques de la table d'acheminement. En outre, une représentation du vecteur binaire (8) contenant les données d'une coupe transversale de l'arbre de préfixes (7) à une profondeur courante (D) et un ensemble de pointeurs comprenant des indices désignant la table Saut Suivant et un fragment Niveau Suivant sont mémorisés. Ledit vecteur binaire (8) est divisé en des masques binaires et une représentation de ces masques binaires est mémorisée dans une table de correspondances. Ensuite, un ensemble de mots de code, chacun codant une rangée d'indices dans la table de correspondances et un décalage de pointeur, ainsi qu'un ensemble d'adresses de base sont mémorisées. La recherche est enfin effectuée.
Brodnik Andrej
Carlsson Svante
Degermark Mikael
Pink Stephen
Borden Ladner Gervais Llp
Brodnik Andrej
Carlsson Svante
Degermark Mikael
Effnet Group Ab
LandOfFree
Method and system for fast routing lookups does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and system for fast routing lookups, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and system for fast routing lookups will most certainly appreciate the feedback.
Profile ID: LFCA-PAI-O-1971775