Flexible routing tables: Designing routing algorithms for overlays based on a total order on a routing table set
Flexible routing tables: Designing routing algorithms for overlays based on a total order on a routing table set
复制标题
DOI：
10.1109/p2p.2011.6038664
复制
发表时间：
2011-10
期刊：
影响因子：
--
通讯作者：
Hiroya Nagao;Kazuyuki Shudo
中科院分区：
文献类型：
--
作者：
Hiroya Nagao;Kazuyuki Shudo
本文提出了灵活路由表（FRT），这是一种设计覆盖网络路由算法的方法。 FRT 有助于扩展路由算法以反映节点标识符以外的因素。基于FRT的算法在路由表的所有模式的集合上定义总顺序，并根据该顺序执行基于标识符的路由。该算法通过可达性保证、条目学习和条目过滤三个操作，沿着顺序逐步细化其路由表。本文提出了 FRT-Chord，一种基于 FRT 的分布式哈希表，并证明它实现了 O(log N) 跳查找。其实施实验表明，路由表细化过程按设计进行。还提出了分组FRT（GFRT），它将节点组引入到FRT中，以证明FRT的灵活性。与 Chord 和 FRT-Chord 相比，GFRT-Chord 导致节点组之间的路由跳数更少。
This paper presents Flexible Routing Tables (FRT), a method for designing routing algorithms for overlay networks. FRT facilitates extending routing algorithms to reflect factors other than node identifiers. An FRT-based algorithm defines a total order on the set of all patterns of a routing table, and performs identifier-based routing according to that order. The algorithm gradually refines its routing table along the order by three operations: guarantee of reachability, entry learning, and entry filtering. This paper presents FRT-Chord, an FRT-based distributed hash table, and gives proof that it achieves O(log N)-hop lookups. Experiments with its implementation show that the routing table refining process proceeds as designed. Grouped FRT (GFRT), which introduces node groups into FRT, is also presented to demonstrate FRT's flexibility. GFRT-Chord resulted in a smaller numbers of routing hops between node groups than both Chord and FRT-Chord.