TBC

RID forwarding differs from that of typical XIDs. HID, SID or CID lookups are based on exact matching, and equivalent to searching in an hash table. On the other hand, RID lookups are based on a longest partial matching method, as explained in Fig. 2 below. The purpose of this method is to mimic longest (name) prefix matching, using 160 bit arrays built out of Bloom Filters.

<add fig. 2>

RIDs do not use the typical forwarding table implementation of XIA - XIAXIDRouteTable - and instead use a dedicated implementation based on PATRICIA tries, XIARIDRouteTable. PATRICIA tries are suitable for this use case, particularly when compared to an hash table.

Searching for the longest partial match (note: not the exact match) in a hash table with N keys is inefficient, taking O(N) time complexity, in all cases. We must always pass through all N keys to be sure we have the longest partial match. To improve efficiency, we should reduce the number of visited keys visited per lookup. PATRICIA tries allow us to do that by discarding groups of keys which are guaranteed to not match the search key.

PATRICIA tries organize keys as a 'compressed' binary trie, i.e. each child shares a prefix of k bits (an array of 0s and 1s) with the parent. k can be different among different parents. Fig. 3 provides an example of a PATRICIA trie of RIDs (for presentation purposes, we shortened RIDs to be 8 bit long).

<add fig. 3>