Method of forwarding data packets, method of creating merged FIB key entry and method of creating a search key
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.
1. A method of creating a key entry of a merged forwarding information base (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;
identifying a common root in a plurality of the RI FIB entries, wherein the merged FIB key entries have the corresponding RII immediately after the common root of the corresponding RI FIB key entries.
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 1 further comprising storing a value of the common root in a memory.
6. The method of claim 5 further comprising creating a search key by inserting the corresponding routing instance identifier in a destination address of a data packet to be routed after a number of bits corresponding to the value of the common root.
7. A method of creating a search key for at least two routing instances (RI) on a network node sharing a merged forwarding information base (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; and
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.
8. The method of claim 7 wherein the RII is inserted at the end of the destination address.
9. The method of claim 7 wherein the RII is inserted between two portions of the destination address.
10. A method of forwarding a data packet with a network node having at least two routing instances (RIs) sharing a merged forwarding information base (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, wherein creating the search key includes inserting the RII after a number of bits of the destination address corresponding to the value of a common root of a plurality of key entries of FIBs of the routing instances;
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.
11. The method of claim 10 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 a memory.
12. The method of claim 11 wherein the 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.
13. The method of claim 11 , wherein the identifying includes identifying a plurality of common roots in key entries of a plurality of FIBs in different private address spaces.
14. The method of claim 13 , wherein the common roots have the same length.
15. The method of claim 14 wherein at least some of the common roots have a different length.
16. The method of claim 10 wherein looking up the merged FIB includes performing a multibit trie algorithm.