A novel model to analyze the performance of routing lookup algorithms
A novel model to analyze the performance of routing lookup algorithms
复制标题
DOI：
10.1109/icct.2003.1209129
复制
发表时间：
2003-04
期刊：
影响因子：
--
通讯作者：
Zhiyong Liang;Xu Ke;Jianping Wu
中科院分区：
文献类型：
--
作者：
Zhiyong Liang;Xu Ke;Jianping Wu
为了实现报文的快速、正常转发，路由器不仅需要快速查找路由表，还需要及时更新路由表。由于读写路由表之间的冲突，更新必须对查找产生一些影响。为了量化这些影响，我们提出了一个基于排队论的性能模型。该模型主要分析了更新对查找吞吐量和延迟的影响。我们还将该模型应用于快速查找算法- 24-8多位尝试。我们检查了建模结果，并提出了一种高效的更新算法，该算法大大提高了24-8位尝试的更新性能，并减少了更新对查找性能的影响。除了24-8位尝试外，该模型还可以应用于其他路由查找算法。
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.