Reading a bit about the subject of Multi-Bit tries and IP matching in:

High Performance Switches and Routers H. Jonathan Chao, Bin Liu. Page 33

Network Routing: Algorithms, Protocols, and Architectures (The Morgan Kaufmann Series in Networking) April 12, 2007 by Deepankar Medhi. Page 507.

And they both mention path compression but they do not explain how to apply path compression to Multi-Bit tries (they only mention that this could be done).

I would like to understand how one would path compress (not level compress) a $k$-Bit trie? What would be the the asymptotic number of nodes given $N$ entries and $w$ width addresses?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.