A method for designing proximity-aware routing algorithms for structured overlays
Takehiro Miyao, Hiroya Nagao, Kazuyuki Shudo · 2013
In many structured overlays, nodes strictly maintain their routing tables using node identifiers. However, building routing tables while taking account of the physical network is difficult. We propose proximity-aware flexible routing tables (PFRT) in this paper as a method to systematically design proximity-aware routing algorithms for structured overlays. PFRT was developed by extending the flexible routing tables (FRT) method such that network proximity is considered. Routing tables in FRT-and PFRT-based algorithms are updated according to the order of the set of all routing table patterns. FRT-based algorithms define a total order based on node identifiers, whereas PFRT-based algorithms define two total orders based on node identifiers and network proximity. Because PFRT is a simple extension of FRT, PFRT-based algorithms also have many of the advantageous features of FRT. We extended Chord to design PFRT-Chord, which is a PFRT-based algorithm. Experimental results showed that PFRT-Chord preserves the expected FRT-derived properties and it could take account of network proximity.