METHOD OF FORWARDING DATA PACKETS, METHOD OF CREATING MERGED FIB KEY ENTRY AND METHOD OF CREATING A SEARCH KEY

Abstract

The method of creating a key entry includes inserting a routing instance identifier (RII) after at least a portion of a key entry of a routing instance (RI) FIB, in accordance with an encoding scheme. In other words, at least a portion of bits of the RI FIB key entry is located before bit(s) of the RII in the resulting, merged FIB key entry. Depending on the encoding scheme, the RII can be inserted at the end of the RI FIB key entry, or at an intermediary location within the RI FIB key entry (after a given number of bits). To form the merged FIB, the method is repeated multiple times on corresponding key entries of the RI FIB. There is also provided a method of creating a search key to lookup the merged FIB.

Claims

1. A method of creating a key entry of a merged FIB for at least two routing instances (RI) on a network node, each RI having a corresponding RI FIB with corresponding RI FIB key entries and a corresponding routing instance identifier (RII), the method comprising: inserting a corresponding RII after at least a portion of a corresponding RI FIB key entry.

2. The method of claim 1 wherein the RII is inserted at the end of the corresponding RI FIB key entry.

3. The method of claim 1 wherein the RII is inserted between two portions of the corresponding RI FIB key entry.

4. The method of claim 1 further comprising repeating the step of inserting on all the RI FIB key entries to create other merged FIB key entries, creating the merged FIB using all the merged FIB key entries.

5. The method of claim 4 further comprising identifying a common root in a plurality of the RI FIB key entries, wherein the merged FIB key entries have the corresponding RII immediately after the common root of the corresponding RI FIB key entries.

6. The method of claim 5 further comprising storing a value of the common root in a memory.

7. The method of claim 6 further comprising creating a search key by inserting the corresponding routing instance identifier in the destination address of the data packet to be routed after a number of bits corresponding to the value of the common root.

8. A method of creating a search key for at least two routing instances (RI) on a network node sharing a merged FIB having key entries, each RI having a corresponding routing instance identifier (RII), the key entries of the merged FIB each including a corresponding one of the RIIs, the method comprising: inserting a corresponding RII after at least a portion of a destination address of a data packet to be routed by the network node.

9. The method of claim 8 wherein the RII is inserted at the end of the destination address.

10. The method of claim 8 wherein the RII is inserted between two portions of the destination address.

11. The method of claim 8 further comprising retrieving a value of a common root from a memory, wherein the RII is inserted after a number of bits of the destination address corresponding to the value of the common root.

12. A method of forwarding a data packet with a network node having at least two routing instances (RIs) sharing a merged FIB, the merged FIB having key entries provided in a format including a routing instance identifier (RII) after at least a portion of a data packet address, in accordance with an encoding scheme, the method comprising: receiving the data packet; reading a destination address in the data packet; creating a search key by inserting a corresponding RII after at least a portion of the destination address, in accordance with the encoding scheme; selecting an output port for the data packet including looking up the merged FIB using the search key; and forwarding the data packet via the selected output port.

13. The method of claim 12 further comprising identifying at least one common root of a plurality of key entries of FIBs of the routing instances, and storing at least one corresponding common root value in the memory, wherein the step of creating the search key includes reading the value of the common root in the memory, and inserting the RII after a number of bits of the destination address corresponding to the value of the common root.

14. The method of claim 13 wherein the step of identifying includes identifying at least one common root of a plurality of key entries of a plurality of FIBs in a same private address space.

15. The method of claim 13, wherein the step of identifying includes identifying a plurality of common roots in key entries of a plurality of FIBs in different private address spaces.

16. The method of claim 16, wherein the common roots have the same length.

17. The method of claim 16 wherein at least some of the common roots have a different length.

18. The method of claim 12 wherein the step of looking up the merged FIB includes performing a multibit trie algorithm.

Description

DESCRIPTION OF THE FIGURES

[0041] In the figures,

[0042] FIG. 1A is a graphical representation of an example method of forming of key entries of a merged FIB;

[0043] FIG. 1B is a graphical representation an example method of forming a search key to lookup the merged FIB of FIG. 1A;

[0044] FIG. 2 is a block diagram showing a network node which can be enabled to perform the methods of FIG. 1A and FIG. 1B;

[0045] FIG. 3A is a graphical representation of an example method of forming of key entries of a merged FIB;

[0046] FIG. 3B is a graphical representation an example method of forming a search key to lookup the merged FIB of FIG. 3A;

[0047] FIG. 4A is a graphical representation of an example method of forming of key entries of a merged FIB;

[0048] FIG. 4B is a graphical representation an example method of forming a search key to lookup the merged FIB of FIG. 4A;

[0049] FIG. 5 is a flow chart of a method of forming a merged FIB;

[0050] FIG. 6 is a flow chart of a method of looking up a merged FIB;

[0051] FIG. 7 is a graphical representation of a multibit trie algorithm looking up the merged FIB of FIG. 1A;

[0052] FIG. 8 is a graphical representation of a multibit trie algorithm looking up the merged FIB of FIG. 4A;

[0053] FIG. 9 is a graphical representation of another multibit trie algorithm looking up the merged FIB of FIG. 3A;

[0054] FIG. 10 is a flow chart of a method of looking up two complementary merged FIBs in parallel;

[0055] FIG. 11 is a block diagram of a system for performing the method of FIG. 10.

DETAILED DESCRIPTION

[0056] As presented above, a single device can have more than one co-existing routing instance. Typically, each routing instance (RI) has a corresponding forwarding information base (FIB), which will be referred to herein as the corresponding RI FIB. FIG. 1A shows a simplified example of two RI FIBs 12, 14. Each RI FIB 12, 14 has a number of key entries (labeled P1-P3). In fact, FIG. 1A shows only the key entries of these FIBs 12, 14; the other field(s) of the FIBs 12, 14 such as next hop field, etc., are not shown for further simplicity of illustration. The key entries are used to access the other field(s), and include at least a portion of an IP address (e.g. a prefix having the common most significant bits of a group of IP addresses or a full IP address).

[0057] Each co-existing RI is attributed a routing instance identifier (RII). The RII can be a virtual network identifier (VNI) or a virtual router identifier (VRI) followed by a VNI, for instance, depending on the specific routing instances co-existing on a given device. The key entries of the merged FIB 16 are created by inserting the routing instance identifier (RII) into the key entries of the corresponding RI FIBs 12, 14. More specifically, prefixes P1-P3 in RI FIB 12 are extended by prepending two binary bits 10 and become prefixes eP1-eP3, respectively, in the merged FIB 16. Similarly, prefixes P1-P3 in RI FIB 14 are extended by prepending two binary bits 11 and become prefixes eP4-eP6, respectively, in the merged FIB 16. All the resulting rows of the encoded RI FIBs (encoded key entries and associated data) are then amalgamated into a merged FIB 16. The encoding of the key entries of the RI FIBs 12, 14 is performed in accordance with an encoding scheme. In this example encoding scheme, the RII is inserted at the beginning of the RI FIB 12, 14 initial/original key entries, and the RI FIB 12, 14 initial key entries extend after the corresponding RII in the corresponding key entry of the resulting merged FIB 16.

[0058] The example shown has been simplified for ease of explanation. For instance, an artificial IP address length of 8 bits is used, whereas IPv4 specifies 32 bits and IPv6 specifies 128 bits. Moreover, in a given embodiment, the number of key entries can vary from one FIB to another, the number of FIBs can vary, and the total length of RII can be of another value than 2 bits. FIBs can be divided into one or multiple private address spaces, and each private address space can have one or more common roots with the same or different length. It will be understood that the teachings of this specification can be applied to alternate embodiments where the address formats are IPv4 or IPv6 address formats, or other formats, and in applications requiring a different number of bits than 2 for the RII. Devices having more than one co-existing routing instance can be embodied in various forms of network nodes, such as routers, network switches, and even personal computers, tablets or smartphones.

[0059] FIG. 2 shows a simplified network node 18 which can have two or more co-existing routing instances. This network node has one processor chip 20 housing one or more processing units 22 connected to a memory system 24. The memory system 24 can have on-chip memory 26 housed within the processor chip 20 and off-chip memory 28. Typically, on-chip memory 26 is much more limited than off-chip memory 28, but can be significantly faster. Typically, network nodes also have additional forms of computer-readable memory, e.g. a hard drive, which can store larger data sets such as heavier software code. The routing instances can be virtually embodied in the network node 18 by software, for instance. In highly specialized network nodes, some of the functions performed by the routing instances, such as the lookup function, for instance, can be partially or fully integrated as part of the processing unit(s) 22.

[0060] For each data packet received by the network node 18, the network node 18 can look up the merged FIB 16 using a single algorithm, independently of the routing instance responsible for the current data packet. More specifically, a search key 32 is created by encoding the destination address 30 of a received data packet in accordance with the encoding scheme. In the example encoding scheme presented in FIG. 1A and FIG. 1B, the search key 32 is created by inserting the corresponding RII at the beginning of the destination address 30 which was read in the received data packet. The search key 32 is compared to the key entries of the merged FIB 16 to find a match, and the data packet is sent through the output interface associated to the matched key entry in the merged FIB. Various algorithms can be used to perform the lookup function, and a selection can be made depending on the specificities of a given application.

[0061] It was found that the encoding scheme presented in FIGS. 1A and 1B, while satisfactory to a certain extent, resulted in limited speed at least in some applications, and that in such applications, greater speed could be achieved by using a different encoding scheme.

[0062] Turning now to FIG. 3A and FIG. 3B, another encoding scheme is presented. In this encoding scheme, the RII is inserted at the end of the addresses and/or prefixes forming the key entries of the RI FIBs 112, 114, to form the merged FIB 116. The same encoding scheme is used to encode the search key 132. The search key 132 is encoded by inserting the RII at the end of the read data packet destination address 130. It was found that greater efficiency/speed could be achieved at least in some applications by using the encoding scheme of FIGS. 3A and 3B instead of the encoding scheme of FIGS. 1A and 1B. This can be the case in applications where the key entries of the RI FIBs were mostly, or all, host routes (full IP addresses). Indeed, in network switches of data centers, for instance, it is quite common for the key entries of the RI FIBs to be mostly, if not all, complete IP addresses as opposed to prefixes. This can be due to factors such as virtual machine moves, for instance.

[0063] Turning now to FIGS. 4A and 4B, another encoding scheme is presented. In this encoding scheme, the RI is inserted in an intermediary location of the addresses or prefixes, and more specifically after a common root of the key entries of the RI FIBs 212, 214, to form the merged FIB 216. The same encoding scheme is used to encode the search key 232. The search key 232 is encoded by inserting the RII at an intermediary location of the read data packet destination address 230. In this encoding scheme, the merged FIB creation algorithm can include a step of identifying common roots of the key entries in the RI FIBs 212, 214. The common root can be in the form of common most significant bits (MSBs) of the key entries, for instance. If common roots are found, the value of the number of bits of the common root can be stored in the memory system, and the RII can be inserted into the RI FIB key entries after the number of bits corresponding to the common root. The rest of the bits of the RI FIB key entries then extend after the RII. Then, to lookup the merged FIB 216, a search key 232 can be encoded by looking up the value of the common root in the memory system, and inserting the RII into the destination address of the data packet after the number of bits corresponding to the common root value. Indeed, it was found that in at least some applications where the key entries of the RI FIBs were mostly prefixes as opposed to full IP addresses, the encoding scheme of FIGS. 4A and 4B provided greater efficiency/speed than the encoding schemes of FIGS. 1A and 1B, and of FIGS. 3A and 3B. If no common roots are found (common root of 0 bits), the algorithm can be designed to default on inserting the RII at the beginning of the RI FIB key entries, for instance.

[0064] Accordingly, in accordance with a general aspect, there is provided a computer-implemented method of encoding a search key or a merged FIB key entry, wherein the encoded key has an RII after at least a portion of the initial key (e.g. after a common root value or at the end of the initial key). The key to be encoded can be a key entry of an RI FIB, to form an encoded key entry of a merged FIB, or a destination address of a data packet, to form a search key. The encoded key, either in the form of an encoded key entry or in the form of a search key, is typically stored in the memory of the device, but can alternately be stored in another form of memory accessible by the network node.

[0065] Indeed, with reference to FIG. 5, a method of forming a merged FIB can include, at step 34, providing a plurality of FIBs of corresponding routing instances co-existing on a given device, and, at step 36, providing routing instance identifiers (RII) for each of these FIBs. The method can further include, at step 38, encoding the key entries of the RI FIBs by inserting the RII after at least a portion of the initial key entries. The merged FIB can then consist of the combined entries of the RI FIBs, with the encoded key entries. If the method is used in accordance with the encoding scheme of FIGS. 3A and 3B, an additional step 40 may be introduced, involving finding a common root of the key entries and storing the value of the number of bits of the common root in a memory for use during step 38 of encoding the key entries or later in step 48 of encoding the search key.

[0066] With reference to FIG. 6, a method of forwarding a data packet can include, at step 42, receiving the data packet; at step 44, reading a destination address of the data packet; at step 48, creating the search key by encoding the destination address based on the encoding scheme; at step 50, looking up the merged FIB using the search key; and, at step 52, forwarding the data packet in accordance with the result of the lookup. Indeed, the encoded key entries of the merged FIB can have forwarding information associated therewith, which directs the forwarding of the data packet via the appropriate output port. It will be noted that here also, if the method is used in accordance with the encoding scheme of FIGS. 3A and 3B, an additional step 46 can be performed, involving looking up the value of the number of bits of the common root to determine how to encode the destination address.

[0067] Example Embodiments Using Multiple Trie Lookup Algorithms

[0068] Various forms of longest prefix match (LPM) lookup algorithms exist. A hash function is one example. The unibit trie is another example. In the unibit trie, the algorithm checks the bits one at a time for a matching prefix until it reaches a ‘dead end’. The dead end can be a bit corresponding to a given prefix length for which the value does not match any longer key entry in the table. Another longest prefix matching algorithm is the multibit trie in which the bits are checked by groups of fixed or variable size referred to as strides in an attempt to gain speed over the unibit trie. The selection of a stride size can be based on a trade-off between memory accesses and space requirements. Several variants of such algorithms exist.

[0069] On-chip search engines are generally used for devices such as data center switches and routers, as search throughput of network processing units (NPUs) can significantly exceed the speed of off-chip memory. Multibit trie algorithms have been used in the past as a satisfactory solution to longest prefix match lookups in such applications. However, when applied to merged FIBs of virtual networks now widely used in software defined networking (SDN) and network function virtualization (NFV), the efficiency of multibit trie algorithms can be limited, at least in applications where the multibit trie is sparsely populated, as sparsely populated multibit tries are relatively costly in terms of on-chip resources. An approach making the multibit trie less sparsely populated was sought.

[0070] Indeed, FIG. 7 shows an example multibit trie algorithm based on the example key encoding scheme presented in FIGS. 1A and 1B. In this algorithm, a shared binary trie 54 is created to represent the merged FIB, and a multi-bit-trie-based algorithm 56 is run on the trie to implement LPM lookup.

[0071] A shared binary trie 54 is created to represent the merged FIB. The shared binary trie is divided into sub-tries T1-T6 according to a stride size of 3. A sub-trie is characterized by prefixes contained within the sub-trie, its child sub-tries, and pointer to a Rout Entry (RE) node array, where an RE node array stores next-hop information for prefixes within a sub-trie. Various encoding schemes, such as internal bitmap for prefixes and external bitmaps for child sub-tries, can be used to encode a sub-trie.

[0072] To lookup address 8′b00011011 that belongs to FIB 1, a search key 10′b1000011011 is created by prepending it with RII of 10. The root sub-trie T1 is checked first against the first stride 100. There is no prefix match in T1, and child sub-trie T2 is chosen. Then the second stride 001 is checked against sub-trie T2, and a match with eP1 is found. Accordingly, eP1 is recorded as the current LPM, and child sub-trie T4 is chosen. Lastly, the third stride 101 is checked against sub-trie T4, and two matches are found: eP2 and eP3. As eP3 has longer length than eP2, eP3 is chosen as the LPM for this stride. Since eP3 has longer length than the current LPM eP1, eP3 is chosen as the final LPM.

[0073] There are two shortcomings for the above approach. First, all prefixes in RI FIB 12 and RI FIB 14 share the same 3 Most Significant Bits (MSBs) 000, and this is not used to achieve higher memory utilization. Secondly, compared with the original FIBs such as FIB 12 and FIB 14, the merged FIB becomes sparser. Sparse tries can render bitmap encoding inefficient, which, in turn, can lead to lower memory efficiency.

[0074] FIG. 8 shows another example multibit trie algorithm 256 applied to the same RI FIBs 212, 214, but encoded in accordance with the key encoding scheme shown in FIGS. 4A and 4B. Here, the RI FIBs are read and a common root of 3 MSBs is found. The corresponding RII is inserted after the common root. A shared binary trie 254 is created to represent the merged FIB. The shared binary trie is divided into sub-tries T1-T5 according to a stride size of 3.

[0075] To lookup address 8′b00011011 that belongs to RI FIB 1, a search key 10′b0001011011 is created by inserting it with RII of 10 after the common root of 000. The root sub-trie T1 is checked first against the first stride 000. There is no prefix match in T1, and child sub-trie T2 is chosen. Then the second stride 101 is checked against sub-trie T2, and a match with eP1 is found. Accordingly, eP1 is recorded as the current LPM, and child sub-trie T3 is chosen. Lastly, the third stride 101 is checked against sub-trie T3, and two matches are found: eP2 and eP3. As eP3 has longer length than eP2, eP3 is chosen as the LPM for this stride. Since eP3 has longer length than the current LPM eP1, eP3 is chosen as the final LPM.

[0076] For emerging Software Defined Networks (SDN) and Network Function Virtualization (NFV), each customer is assigned a Virtual Network, where resources allocated to a Virtual Network include a set of virtual machines and an IP address block. There are two standard IP address formats, an IPv4 address format with a length of 32 bits, and an IPv6 address format with a length of 128 bits. Typically, private IPv4 or IPv6 addresses are used for the IP address block assignment, and a virtual machine is assigned a private IPv4 or IPv6 address. As an example, a customer A can be assigned an IPv4 address block of 192.168/16, where /16 means that all customer A's addresses has the same 16 bit prefix 192.168, and another customer B can be assigned an IPv4 address block of 192.168.20/24. Here, 192.168/16 and 192.168.20/24 are called prefix roots for customers A and B, respectively. As these two customers have overlapping IPv4 address blocks, they must be assigned different RIIs for proper routing.

[0077] For IPv4, there are three private address spaces: 10/8, 172.16/12, and 192.168/16. For IPv6, many private address spaces are available, where a private address space is identified by a 7 bit fixed prefix plus a 40 bit global ID. A customer is assigned an address block within a private address space.

[0078] The above FIB merging shown in FIG. 8 can be extended to cover multiple private address spaces defined for both IPv4 and IPv6. This can be done in accordance with the following steps: [0079] A. within each private address space, find the shared MSBs among FIBs in the private address space, and these shared MSBs are defined as common roots of these FIBs; [0080] B. a prefix in a VR or VPN FIB is extended by inserting RII (VRI or VPNI) immediately after the common root; [0081] C. a merged FIB for the private address space is generated from the set of extended prefixes from all VRs and VPNs assigned to the private address space; [0082] D. merged FIBs from all private address spaces are aggregated into one larger merged FIB; [0083] E. a trie is created for the (overall) merged FIB; and [0084] F. an efficient multi-bit-trie-based algorithm is run on the trie to implement an LPM lookup.

[0085] Turning now to FIG. 9, another example multibit trie algorithm 156 is shown. In this example, the multibit trie algorithm 156 is applied to the context of a key encoding scheme of FIGS. 3A and 3B. Regardless of private address spaces, a host route is extended by appending the RII immediately after the host route.

[0086] A merged FIB 116 is generated from the set of extended host routes from all routing instances (such as VPNs or VRs). A merged trie 154 is created to represent the merged FIB 116.

[0087] In the scenario shown in FIG. 7, even though FIB 12 and FIB 14 share the same host routes P1-P3, their extended host routes eP1 and eP4 as well as eP3 and eP6 were very far apart from each other in the merged FIB, which limits memory efficiency.

[0088] By appending the RII after the host route, for the host route P1 shared by FIB 112 and FIB 114, their extended host routes eP1 and eP4 are very close to each other, in the same subtrie T3 of the merged FIB 116. Similarly, for the host route P3 shared by FIB 112 and FIB 114, their extended host routes eP3 and eP6 are very close to each other, in the same subtrie T6 of the merged FIB 116. As a result, higher memory efficiency is achieved in the merged FIB 116.

[0089] Indeed, in modern data centers, most entries in a FIB are host routes due to virtual machine moves, where a host route is assigned to a single host and has a length of 32 bits or 128 bits for IPv4 or IPv6, respectively. As all host routes for a given address format have the same length.

[0090] Referring to FIG. 10, in a more evolved approach, prefix keys and IP address (or host route) keys can be encoded differently into separate, partial, merged FIBs, and the separate FIBs can be looked up separately at steps 62 and 64, in parallel, after reading the destination address at step 60. The results of the IP address lookup can be given priority in a manner that the prefix key lookup result is treated as a match only if, at step 66, the IP address key lookup has failed to identify a result.

[0091] Indeed, for IP lookups of virtual networks two multi-bit merged tries can be generated, one for prefix RI key entries in which the RII is inserted after a common root, and another one for host route key entries in which the RII is appended to the host route. Such an embodiment is illustrated in FIG. 11.

[0092] Here, two parallel multi-bit trie lookup functions 72, 74 are performed, one for merged prefix FIB 72, the other for merged host route FIB 74. A priority encoder 76 is used to select the best match among the parallel lookup results, where the results from the merged host route FIB are given higher priority. If a match is found from the merged host route FIB function 74, the match is selected as the final LPM match, otherwise, the match from the merged prefix FIB lookup function 72 is selected as the final LPM match.

[0093] Indeed, simulations have demonstrated that for IPv4 using address block of 192.168/16, the solution can provide more than 30% in memory savings, whereas in a private address block scenario under IPv6, the solution can provide memory savings up to 50%.

[0094] As can be understood, the examples described above and illustrated are intended to be exemplary only. For instance, the methods presented above can be applied to processor chips for servers or other applications having similar search engine capabilities where key entries having an address format need to be looked up for matching. The key encoding scheme can be applied to other forms of lookup algorithms, such as search tree-based algorithms. The scope is indicated by the appended claims.