دانلود رایگان مقاله CONSERT: ساخت بهینه جداول مسیریابی بر اساس نام

Abstract

Name-based routing belongs to a routing category different from address-based routing, it is usually adopted by content-oriented networks [Sharma et al., 2014, Koponen et al., 2007, Rajahalme et al.,2011, Thaler et al.,1998, Hwang et al., 2010, Gritter et al., 2001, Caesar et al., 2006, Carzaniga et al., 2004, Koponen et al., 2007, Hwang et al., 2009 Singla et al., 2010, Detti et al., 2011, Jain et al., 2011 Xu et al., 2013, Katsaros et al., 2012. 0001, 0002, 0003, 0004, 0005, 0006, 0008, 0009, 0010, 0011, 0012, 0013, 0014, 0015 and 0016] e.g., the recently proposed Named Data Networking (NDN). It populates routers with name-based routing tables, which are composed of name prefixes and their corresponding next hop(s). Name-based routing tables are believed to have much larger size than IP routing tables, because of the large amount of name prefixes and the unbounded length of each prefix. This paper presents CONSERT—an algorithm that, given an arbitrary name-based routing table as input, computes a routing table with the minimal number of prefixes, while keeping equivalent forwarding behavior. The optimal routing table also supports incremental update. We formulate the CONSERT algorithm and prove its optimality with an induction method. Evaluation results show that, CONSERT can reduce 18% to 45% prefixes in the synthetic routing tables depending on the distribution of the next hops, and meanwhile improve the lookup performance by more than 20%. Prior efforts usually focus on compact data structures and lookup algorithms so as to reduce memory consumption and expedite lookup speed of the routing table, while CONSERT compresses the routing table from another perspective: it removes the inherent “redundancy” in the routing table. Therefore, CONSERT is orthogonal to these prior efforts, thus the combination of CONSERT and a prior compressing method would further optimize the memory consumption and lookup speed of the routing table. E.g., we can first adopt CONSERT to achieve the optimal routing table, and afterwards apply NameFilter [Wang et al., 2013. [16], a two-stage-Bloom-filter method, to that optimal table. This combination diminishes the memory consumption of the routing table data structure by roughly 88%, and increases the lookup throughput by around 17% simultaneously. The joint method outperforms each individual method in terms of memory savings and absolute lookup throughout increase.

7. Conclusion

This paper proposes an algorithm called CONSERT to build an optimal name-based routing table with the minimal number of prefixes. CONSERT consists of three passes, where Pass One introduces the ‘#’ symbol and pushes the next hops down to the ‘#’ nodes, Pass Two pushes the most prevalent next hop(s) upwards as high as possible, and Pass Three determines the next hop for each prefix. CONSERT can apply to the situations of no default route and multiple next hops, and it works for tries of different granularities as well. We formulate the algorithm and prove its optimality using the induction method. Experimental results show that CONSERT can effectively reduce the number of prefixes in a routing table and improve the lookup performance, especially cooperates with other orthogonal data structure compressing methods like NameFilter.