Efficient Partitioning of the Binary Trie to Keep IPv6 Forwarding Tables in cache Memories
Resumen: Different bit-vector encoding schemes of the forwarding table guarantee low and constant lookup latency in Longest Prefix Matching (LPM) lookups; however those schemes have an exponential memory complexity and no proposal justifies fully the parameter values used in the encoding. Usually the encoding parameters can be seen as cuts in a binary Trie and cuts belong to combination problem; also the updates of forwarding tables is once or twice times in a second then, the combination problem has to solved in a short time. We use heuristic search to find the best combination that gives an efficient partitioning of the Trie in terms of memory and LPM instructions.
Última actualización: May 29, 2016 at 18:20 pm