H - Electricity – 04 – L
Patent
H - Electricity
04
L
H04L 29/06 (2006.01)
Patent
CA 2520769
The present invention provides a technique for efficiently looking up addressrouting information in an intermediate network node, such as a router. To that end, the node locates routing information stored in its memory using one or more "lookup" tables (LUT) which can be searched using a small, bounded number of dependent lookups, thereby reducing the number of dependent lookups conventionally performed. The LUTs are arranged so each table provides routing information for network addresses whose subnet mask lengths are within a different range ("stride") of mask lengths. According to the technique, the node locates a network address's routing information by searching the LUTs, in order of decreasing prefix lengths, until the routing information is found. Preferably, several tables are searched in parallel. A match in a LUT may further point to a small MTRIE that enables the final bits of a prefix to be matched. That final MTRIE is searched using a relatively small, bounded number of dependent lookups.
L'invention concerne une technique pour une consultation efficace d'informations de routage d'adresse dans un noeud de réseau intermédiaire, notamment un routeur. A cet effet, le noeud localise des informations de routage stockées dans sa mémoire au moyen d'au moins une table de consultation (LUT) dans laquelle des recherches peuvent être effectuées au moyen d'un nombre restreint de consultations dépendantes, ce qui permet de réduire le nombre de consultations dépendantes classiquement effectuées. Les LUT sont agencées de sorte que chaque table fournisse des informations de routage pour des adresses de réseau dont les longueurs de masque de sous-réseau sont comprises à l'intérieur d'une plage différente (<= foulée >=) de longueurs de masque. Selon la technique de l'invention, le noeud localise des informations de routage d'adresse de réseau par une recherche des LUT, de sorte à réduire des longueurs de préfixe, jusqu'à ce que les informations de routage soient trouvées. De préférence, on effectue des recherches dans plusieurs tables, en parallèle. Une correspondance de LUT peut indiquer plus avant un petit MTRIE permettant une mise en correspondance des BITS finaux d'un préfixe. Puis, on effectue des recherches dans le MTRIE final au moyen d'un nombre relativement restreint de consultations dépendantes.
Barach David R.
Batacharia Bobby
Cisco Technology Inc.
Gowling Lafleur Henderson Llp
LandOfFree
A bounded index extensible hash-based ipv6 address lookup... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with A bounded index extensible hash-based ipv6 address lookup..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A bounded index extensible hash-based ipv6 address lookup... will most certainly appreciate the feedback.
Profile ID: LFCA-PAI-O-1659523