# US 10,454,825 B2 · Hybrid routing table for routing network traffic > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 10,454,825 B2 - Document ID: US10454825B2 - Status: Granted - Kind: B2 - Application number: 15/807,042 - Filed: 2017-11-08 - Published: 2019-05-09 - Granted: 2019-10-22 - Earliest claimed: 2017-11-08 - Assignees: Nicira, Inc. - Applicants: Nicira, Inc. - Inventors: Xinhua Hong; David Leroy; Yong Wang; Jia Yu - Web page: https://patentgrep.com/patent/US10454825B2 ## CPC - H04L 45/7453: using hashing - H04L 45/74: Address processing for routing - H04L 45/745: Address table lookup; Address filtering - H04L 45/741: Routing in networks with a plurality of addressing schemes, e.g. with both IPv4 and IPv6 - H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M) ## Abstract The technology disclosed herein enables network traffic routing using a hybrid routing table. In a particular embodiment, a method provides adding a first portion of a network prefix to one or more tiers of one or more tries in the hybrid routing table. Upon reaching a lowest node of the one or more tries when adding the first portion of the network prefix, the method provides adding key information to the lowest node. The key information and at least a second portion of the network prefix comprise a key to locate a value in a hash table of the hybrid routing table. The value indicates routing information for the network prefix. Additionally, the method provides routing packets using the hybrid routing table. ## Claims ### Claim 1 A method of using a hybrid routing table to route network packet traffic, the method comprising: adding a first portion of a network prefix to one or more tiers of one or more tries in the hybrid routing table; upon reaching a lowest node of the one or more tries when adding the first portion of the network prefix, adding key information to the lowest node, wherein the key information and at least a second portion of the network prefix comprise a key to locate a value in a hash table of the hybrid routing table, wherein the value indicates routing information for the network prefix; and routing packets using the hybrid routing table. ### Claim 2 (depends on 1) The method of claim 1, wherein routing packets using the hybrid routing table comprises: receiving a packet addressed to a network address having the network prefix; traversing the one or more tiers of tries using the first portion of the network prefix; using the key to locate the value in the hash table; and sending the packet to a next hop indicated by the routing information. ### Claim 3 (depends on 1) The method of claim 1, further comprising: inputting the key information and the second portion of the network prefix as inputs into a hash function, resulting in the key being generated as output of the hash function. ### Claim 4 (depends on 1) The method of claim 1, wherein the key information includes a Virtual Routing and Forwarding (VRF) identifier. ### Claim 5 (depends on 1) The method of claim 1, wherein the first portion of the network prefix comprises the outer 32 bits of an Internet Protocol version 6 (IPv6) network address. ### Claim 6 (depends on 5) The method of claim 5, wherein the second portion of the network prefix includes a remaining 0 to 32 bit portion of the network prefix. ### Claim 7 (depends on 1) The method of claim 1, wherein the one or more tries comprises a 4 level trie with each level representing 8 bits. ### Claim 8 (depends on 1) The method of claim 1, wherein the value comprises a pointer to the routing information. ### Claim 9 (depends on 1) The method of claim 1, wherein adding the first portion to the one or more tiers of one or more tries comprises: at each trie node of the one or more tries that is traversed, other than the origin node, including a previous node indicator, which indicates the previous trie node in the traversal. ### Claim 10 (depends on 9) The method of claim 9, wherein the value further indicates the lowest node and the method further comprising: removing the routing information from the routing table, wherein removing the routing information comprises: deleting the routing information and the value; identifying the lowest node as indicated by the value; and from the lowest node upward, using the previous node indicator included at each trie node to remove the first portion from the one or more tries. ### Claim 11 An apparatus for using a hybrid routing table to route network packet traffic, the apparatus comprising: one or more computer readable storage media; a processing system operatively coupled with the one or more computer readable storage media; and program instructions stored on the one or more computer readable storage media that, when read and executed by the processing system, direct the processing system to: add a first portion of a network prefix to one or more tiers of one or more tries in the hybrid routing table; upon reaching a lowest node of the one or more tries when adding the first portion of the network prefix, add key information to the lowest node, wherein the key information and at least a second portion of the network prefix comprise a key to locate a value in a hash table of the hybrid routing table, wherein the value indicates routing information for the network prefix; and route packets using the hybrid routing table. ### Claim 12 (depends on 11) The apparatus of claim 11, wherein to route packets using the hybrid routing table, the program instructions direct the processing system to: receive a packet addressed to a network address having the network prefix; traverse the one or more tiers of tries using the first portion of the network prefix; use the key to locate the value in the hash table; and send the packet to a next hop indicated by the routing information. ### Claim 13 (depends on 11) The apparatus of claim 11, wherein the program instructions further direct the processing system to: input the key information and the second portion of the network prefix as inputs into a hash function, resulting in the key being generated as output of the hash function. ### Claim 14 (depends on 11) The apparatus of claim 11, wherein the key information includes a Virtual Routing and Forwarding (VRF) identifier. ### Claim 15 (depends on 11) The apparatus of claim 11, wherein the first portion of the network prefix comprises the outer 32 bits of an Internet Protocol version 6 (IPv6) network address. ### Claim 16 (depends on 15) The apparatus of claim 15, wherein the second portion of the network prefix includes a remaining 0 to 32 bit portion of the network prefix. ### Claim 17 (depends on 11) The apparatus of claim 11, wherein the one or more tries comprises a 4 level trie with each level representing 8 bits. ### Claim 18 (depends on 11) The apparatus of claim 11, wherein the value comprises a pointer to the routing information. ### Claim 19 (depends on 11) The apparatus of claim 11, wherein to add the first portion to the one or more tiers of one or more tries, the program instructions direct the processing system to: at each trie node of the one or more tries that is traversed, other than the origin node, include a previous node indicator, which indicates the previous trie node in the traversal. ### Claim 20 (depends on 19) The apparatus of claim 19, wherein the value further indicates the lowest node and the program instructions further direct the processing system to: remove the routing information from the routing table by: deleting the routing information and the value; identifying the lowest node as indicated by the value; and from the lowest node upward, using the previous node indicator included at each trie node to remove the first portion from the one or more tries.