Vol. 50 No. 9 2298 2311 (Sep. 2009) ID/Locator 1 2, 3 3 ID locator ID/Locator ID ID Transport IP locator Locator Transport ID locator P2P PIAX 10,000 1% A Mechanism of ID/Locator Separation in Overlay Networks Mikio Yoshida, 1 Yuuichi Teranishi 2, 3 and Shinji Shimojo 3 In this paper, we propose a new mechanism to separate an identifier (ID) of a node and its locator for overlay networks. In this mechanism, there are two transport layers, ID transport and locator transport. ID transport has its own routing algorithm to forward messages according to the ID of each node. Locator transport forwards messages to the neighbor nodes according to node locators such as IP addresses. This mechanism does not require external name (ID) resolvers. Moreover, as long as the routing table of the overlay network is symmetric, handover is carried out efficiently. This mechanism also enhances the node mobility and enables transparent messaging across multiple physical networks. Implementation of the proposed mechanism on the P2P platform PIAX confirmed its feasibility and effectiveness. Moreover, by simulations using this implementation, the message transmission error ratio is approximately less than 1% even in the overlay network which consists of 10,000 nodes. 1. IP FQDN IP IP 2 ISP 2 IP identity location IP IP duality of the IP address 1),2) identifier ID locator ID/Locator ID/Locator ID/Locator 1 BBR Inc. 2 Graduate School of Information Science and Technology, Osaka University 3 National Institute of Information and Communications Technology 2008 3 2298 c 2009 Information Processing Society of Japan
2299 ID/Locator ID End-to-End locator ID ZigBee non-ip IP non-ip ID DNS DHT ID locator locator P2P PIAX 3),4) 2 ID/Locator 3 ID/Locator ID/Locator 4 PIAX 5 6 (a) Case: Destination is specified by ID 2. ID/Locator WIDE IETF IP ID/Locator LINA Location Independent Network Architecture 1) HIP Host Identity Protocol Architecture 5) ID 2.1 LINA LIN6 LINA ID/Locator 1 LINA Network 2 ID/Locator ID locator 1 (a) ID (b) locator LINA ID locator ID Network MA Mapping Agent ID (b) Case: Destination is specified by locator 1 LINA Fig. 1 Packet flows in LINA. MA LIN6 Location Independent Networking for IPv6 6) LINA IPv6 LIN6 ID 40 bit LIN6 ID IPv6 64 bit 24 bit locator IPv6 LIN6 MA ID/Locator
2300 ID/Locator 1 DNS DHT Table 1 Comparison of DNS and DHT as the name server. DNS DHT 1 ID P2P 2 2 HI HIT Fig. 2 Generation flows of HI and HIT. 2.2 HIP Architecture HIP Architecture Transport Network ID LINA HIP Architecture 2 LIN6 ID locator locator ID HIP Architecture ID HI Host Identifier HIT Host Identity Tag HI HIT 128 bit HI hash 2 HI HIT LSI Local Scope Identifier IP LIN6 ID MA HIP Architecture ID 2.3 ID LINA HIP Architecture ID ID locator DNS DHT 1 DNS DHT 2 DHT i3 10) secure-i3 11) 2.4 ID/Locator (1) LIN6 IPv6 LIN6 HIP Architecture ID/Locator (2) IP 3 IP 1 LISP 7) ID/Locator LISP3 2 OpenDHT 8) Internet Draft 9)
2301 ID/Locator AP Access Point IP (1) AP (2) AP (3) DHCP IP (1) (2) (3) IP 13) 50 400 msec 3 Fig. 3 Overlapped aspect of physical networks. IP MANET ID/Locator ID (3) ID ID/Locator ID ID DHT ID DHT churn 12) churn 2.5 ID/Locator ID LAN locator locator LAN (3) 14) 2 5 3.34 LAN IP 1 locator locator locator LAN locator 16) MN 2 AP 17) 19) LAN locator locator ID locator locator locator 4 2 locator locator 4 locator L L t 1 locator L t 2 1 IP ZigBee IP 15) non-ip
2302 ID/Locator Fig. 4 4 locator Keep time of old locator in dual locator handling. (a) Case of the IP network locator t 3 ID t 3 t 1 locator ID/Locator locator 1 DHCP IP ID t 3 t 1 3. ID/Locator ID/Locator ID/Locator 3.1 ID/Locator ID/Locator ID Transport ID Transport locator Transport Locator Transport 5 1 MAT locator 18) ID/Locator (b) Case of the overlay network 5 ID/Locator Fig. 5 Routing flows over ID/Locator separation layer. 5 (a) IP ID Transport ID locator 5 (b) ID Transport ID Locator Transport locator (a) (b) (a) A B (b) (b) A X
2303 ID/Locator X B 3 (b) (a) locator (b) locator locator locator 1 3.2 5(b) ID/Locator (1) (2) (3) IP Kademlia 20) Skip Graph 21) 3.3 ID/Locator 6 ID/Locator 6 ID/Locator ID Transport Locator Transport 2 ID Transport ID 6 ID/Locator Fig. 6 Hierarchical architecture includes ID/Locator separation. ID ID locator Locator Transport locator 2 locator Locator Transport locator ID Transport ID ID reachability 2 3.4 7 2 locator locator 1 P Q Q P 2 ID ID
2304 ID/Locator Fig. 8 8 Simultaneous updation between neighbor nodes. Fig. 7 7 Sequence of handover process. 7 L 1 L 2 L 1 L 2 C locator C L 1 L 2 C A C D C locator A D A D L 1 L 2 d 2 d d 2 ID 4 t 3 t 2 2 d t 3 t 2 2 d 8 A B 8 A locator L L B locator M M locator 2 d 4. PIAX 3.3 ID/Locator PIAX PIAX PIAX Multi-key Skip Graph 22) Skip Graph Multi-key Skip Graph Skip Graph 4.1 Overlay Transport 2 PIAX Overlay Transport ID/Locator 9 ID/Locator Overlay Transport 3.3 Overlay Transport ID Transport
2305 ID/Locator (2) IdResolver ID seed ID locator ID LocatorTransport locator (3) LocatorTransport locator LocatorTransportService 9 PIAX Overlay Transport Fig. 9 New overlay transport structure in PIAX. Locator Transport 2 ID Transport Locator Transport IdTransport LocatorTransport PIAX locator PeerLocator Java IP InetSocketAddress PeerLocator locator ID Transport Multi-key Skip Graph IdResolver LocatorTransport LocatorTransportService (1) IdTransport ID IdResolver ID locator LocatorTransport seed 1 IdResolver LocatorTransport 1 locator LocatorTransportService locator LocatorTransportService (4) LocatorTransportService locator LocatorTransport 4.2 (1) ID (2) (3) (1) IdTransport API ID NAT seed NAT LocatorTransportService IdTransport (2) locator locator LocatorTransportService IdResolver
2306 ID/Locator locator Locator Transport 2 locator locator (3) LocatorTransport LocatorTransportService LocatorTransportService LocatorTransportService PIAX ID/Locator ZigBee IP 23) 5. ID 2 HIP DNS DHT 3 ID locator 5.1 ID ID locator ID p log 2 N 1 p 1/4 Pastry 25) 1 Chord 26) Kademlia Skip Graph d DHT ID locator t put ID locator t get DHT 2 DNS DHT DHT 1 2 1 DHT N 2 log N 1 2 ID D hip1 D hip2 D prop ID locator 1 DHT 2 d D hip1 (1) D hip1 = t get +3 d (1) 2 t get p log 2 N DHT 27) slow D hip2 (2) D hip2 =(2 p log 2 N +1) d (2) (3) D prop = p log 2 N d (3) 2 2 1 N 2 log N 1 DHT t get 250 msec d 25 msec 5msec p log 2 N p 1 10 2 10 2 1 100 2 10,000 1 Skip Graph 24) 2 DHT t get 28) d 29)
2307 ID/Locator 5.3 locator locator locator 1 2 locator M hip1 M hip2 M prop locator ID t put + d DHT t put t get M hip1 M hip2 (4) (5) M hip1 =max(t get,t put)+3 d (4) M hip2 =(2 p log 2 N +1) d (5) 10 ID Fig. 10 Comparison of send times to the ID specified node. d p log 2 N p d p 2 10 8 d p 5.2 locator locator ID locator locator locator ID d 3.4 (3) M prop (6) M prop =(c p log 2 N) d (6) c 3 (4) (5) 10 (6) D prop 3 locator M prop 3.4 (7) M prop =2 d (7) M prop 10 50 msec 5.4 (7) PIAX Random Waypoint Model RWP 30) AP 1 RWP 1 AP 100 m AP 50 m
2308 ID/Locator AP thinking time T H C RWP T 60 300 H 5 100 C 1 10 1 LocatorTransportService 1 EmuTransport Service 9 (emulator) EmuTransportService 1 Java VM socket 5 ID/Locator N 100 1,000 10,000 3 25 msec 5msec ID locator 0 100 msec 4 d ID 1,000 11 X ID locator Y 100 1,000 10,000 2 locator 100 1,000 10,000 locator 2 d 1 5km 70 km 11 Fig. 11 Simulation result. 10,000 locator 10,000 1% 6. ID/Locator PIAX
2309 ID/Locator 2.4 (1) 2.4 (2) 4.2 ID ALM ID ID 5.2 ID locator ID locator 2 2.4 (3) ID PIAX 1) Ishiyama, M., Kunishi, M., Uehara, K., Esaki, H. and Teraoka, F.: LINA: A New Approach to Mobility Support in Wide Area Networks, IEICE Trans. Communication, No.8, pp.2076 2086 (Aug. 2001). 2) AKARI AKARI Ver.1.1 (July 2008). http://akari-project.nict.go.jp/index2.htm 3) PIAX: (2006). http://www.piax.org/ 4) P2P PIAX Vol.49, No.1, pp.402 413 (Jan. 2008). 5) Moskowitz, R. and Nikander, P.: Host Identity Protocol (HIP) Architecture, rfc4423, IETF (May 2006). 6) Teraoka, F., Ishiyama, M. and Kunishi, M.: LIN6: A Solution to Multihoming and Mobility in IPv6, Internet-draft, IETF (Dec. 2003). 7) Farinacci, D., Fuller, V., Oran, D. and Meyer, D.: Locator/ID Separation Protocol (LISP), draft-farinacci-lisp-05 (work in progress), IRTF (Nov. 2007). 8) OpenDHT: (2004). http://www.opendht.org/ 9) Henderson, T. and Gurtov, A.: HIP Experiment Report, draft-irtf-hip-experiment- 03 (work in progress), IRTF (Mar. 2007). 10) Stoica, I., Adkins, D., Zhuage, S., Shenker, S. and Surana, S.: Internet Indirection Infrastructure (i3), Proc. ACM SIGCOMM (Aug. 2002). 11) Nikander, P., Arkko, J. and Ohlman, B.: Host Identity Indirection Infrastructure (Hi3), draft-nikander-hiprg-hi3-00, IETF (June 2004). 12) DHT churn Vol.49, No.SIG2 (ACS 21), pp.1 9 (Mar. 2008). 13) Mishra, A., Shin, M. and Srbaugh, W.: An Empirical Analysis of the IEEE 802.11 MAC Layer Handoff Process, ACM SIGCOMM Computer, Communication Review, Vol.33, No.2, pp.93 102 (Apr. 2003). 14) Mobile PPC Vol.47, No.12, pp.3244 3257 (Dec. 2006). 15) (2007). http://forum.nwgn.jp/ 16) Gogo, K., Shibui, R. and Teraoka, F.: An L3-driven fast handover mechanism in IPv6 mobility, Proc. SAINT2006, IPv6 Workshop (Jan. 2006). 17) LAN IN Vol.104, No.438, pp.7 12 (Nov. 2004). 18) MAT-MONET DICOMO 2006 pp.961 964 (July 2006). 19) 44 pp.91 98 (Mar. 2008).
2310 ID/Locator 20) Maymounkov, P. and Mazieres, D.: Kademlia: A peer-to-peer information system based on the XOR metric, Proc. 1st International Workshop on Peer-to-Peer Systems (IPTPS 02 ), Vol.258, p.263 (2002). 21) Aspnes, J. and Shah, G.: Skip graphs, ACM Trans. Algorithms, Vol.3, No.4, p.37 (Nov. 2007). 22) Skip Graph Vol.49, No.9, pp.3223 3233 (Sep. 2008). 23) Fujiwara, K., Teranishi, Y., Takeuchi, S., Harumoto, K. and Nishio, S.: An Implementation of Lightweight Message Transport Mechanism for P2P Agent Platform on Ad-hoc Networks, The 2008 International Symposium on Applications and the Internet (SAINT 2008 ) Workshops on Ubiquitous Networking and Enablers to Context-Aware Services (July 2008). 24) P2P 19 DEWS 2008 (Mar. 2008). 25) Rowstron, A. and Druschel, P.: Pastry: Scalable, decentralized object location and routing for large-scale peer-to-peer systems, Proc. 18th IFIP/ACM International Conference on Distributed Systems Platforms (Middleware 2001 ) (2001). 26) Stoica, I., Morris, R., Karger, D., Kaashoek, F. and Balakrishnan, H.: Chord: A Scalable Peer-To-Peer Lookup Service for Internet Applications, Proc. ACM SIG- COMM, pp.149 160 (2001). 27) SWoPP 2006 pp.9 16 (July 2006). 28) 10 10 ID Vol.49, No.3, pp.1265 1274 (Mar. 2008). 29) B Vol.91, No.10, pp.1182 1192 (Oct. 2008). 30) Johnson, D.B. and Maltz, D.A.: Dynamic Source Routing in Ad Hoc Wireless Networks, Mobile Computing, Imielinski, T. and Korth, H. (Eds.), chapter 5, pp.153 181, Kluwer Academic Publishers (1996). ID Locator ID ID Transport IP Locator Locator Transport 1981 1986 1994 2002 1993 1995 2005 2007 IEEE ( 20 9 7 ) ( 21 6 4 )
2311 ID/Locator 1981 1986 1989 1991 1998 2000 2008 4 ACM IEEE