柔軟な経路表：経路表空間上の順序関係を利用したオーバレイネットワークルーティング方式

摘要

We present "Flexible Routing Tables (FRT)", a method of designing routing algorithm for structured overlay networks. The algorithms based on FRT are able to consider node identifiers without restriction of candidates for routing tables, because they define orders "≦_(ID)" of preferativity for node identifiers in tables, and repeat updating own tables based on the order. We design FRT-Chord, a DHT based on FRT and demonstate that it achieves O(log N)-hop lookup performance. We also implement it and show that its method of constructing routing tables works well and makes path lengthes short.%オーバレイネットワークにおけるルーティングアルゴリズムの構成手法である“柔軟な経路表（FRT）”を提案する．FRTに基づくアルゴリズムは，経路表間の優劣を表す順序関係≦_(ID)を定義し，それに従って経路表の改良を繰り返すことで，経路表構築の際に経路表の候補を限定することなくノードID を考慮できる．FRTに基づくDHTアルゴリズムFRT-Chord を設計し，十分経路表が更新されるとき，経路長がノード数N に対してO（log N）になることを示した．また，FRT-Chordを実装し，FRTの経路表更新手続きが意図したとおりに動作し，経路表を短縮することを確認した．