CONSERT: Constructing optimal name-based routing tables

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