A scalable routing architecture for prefix tries

While the throughput demand for a backbone router keeps increasing constantly, both routing and switching of packets are facing tough challenges for running faster. Currently, the prefix tries based routing algorithms are playing a key role in building high performance routing systems. We proposed in this article a routing architecture for scaling the throughput of a trie-based routing system, which consists of multiple memory blocks for trie storage and a buffer for queuing packets to resolve temporary memory access contentions. Specifically, when a trie is constructed, we store the nodes of the trie evenly into each memory block. The scheduling of queuing packets to access the memory blocks for their routes is modeled as a bipartite matching problem. A queuing model is developed to examine the system´s theoretical performance under some simplified assumptions, and a series of computer simulation experiments are conducted for performance evaluation of the proposed system under more realistic conditions. The results from both the analytical queuing model and the simulation experiments indicate that this architecture can be a potential candidate for building high bandwidth routing engines for backbone routers.