A novel model to analyze the performance of routing lookup algorithms

To forward packets fast and properly, routers need not only perform lookups in the routing table at high speed but also update the routing table in time. Due to confliction between reading and writing the routing table, updates must have some effects on lookups. To quantify the effects, we propose a performance model based on the queuing theory. The model mainly analyzed the effects of updates on lookup throughput and delay. We also apply the model to a fast lookup algorithm - 24-8 multibit tries. We examine the modeling results and present a high efficient update algorithm that greatly improves the update performance of 24-8 multibit tries and lessens the effects of updates on lookup performance. Besides 24-8 multibit tries, the model can also be applied to other routing lookup algorithms.