Distributed ID/Locator Resolution System
for Inter Mesh Networks
Masaaki Ohnishi

Kazuyuki Shudo

Tokyo Institute of Technology
Ookayama 2–12–1, Meguro-ku,
Tokyo, 152–8552, Japan
Email: ohnishi.m.aa@m.titech.ac.jp

Tokyo Institute of Technology
Ookayama 2–12–1, Meguro-ku,
Tokyo, 152–8552 Japan
Email: shudo@is.titech.ac.jp

Abstract—We propose an ID/Locator resolution system forsuper wide area wireless mesh networks constructed using
Delaunay overlay networks. Unlike conventional mobile ad-hoc
network protocols, the proposed system does not use flooding
to spread the locator notification messages of each node. The
proposed method sends one-hop locator notifications on skip links
such as skip graphs. The proposed system realized scalability
by controlling the route, frequency, and storing locations of thelocator notification message. Specifically, when the number ofnodes increases, the average load on communication links andthe message database of each node are approximately O(log n),
where n is the total number of nodes. The scalability of the
proposed method is confirmed through simulations.

I. I NTRODUCTION
The relationships among the elements that comprise thepropsed inter-mesh network concept are shown in Fig. 1. The
lower part of the wireless mesh network group is expected tosupport emergency communication networks, e.g., networks
used by local governments and the Japanese Self-Defense
Forces when responding to disaster situations. We construct asuper-wide area network in which such networks are combined
and integrated by using a Delaunay overlay network [1],which is a type of geo-assisted routing network(Middle layer
in Fig.1). This is expected to be applied to super-wide area
disaster situations such as Nankai Trough great earthquake [2].
For example, a land scale wireless mesh network is constructed by automobile nodes such local governments, polices,
fire departments, hospitals and others. However, the wirelessmesh network to which such vehicle nodes of the scale of
100,000 units belongs can not be constructed by the mainstream wireless mesh network protocols using flooding.
The left of Fig. 2 indicates that the control messages reaches
the entire network from central node due to flooding. The
flooding route is indicated by arrows. All the nodes on theroutes store the control message. This store nodes are indicatedby diagonal lines. The control message includes the ID of thecentral node and the ID of its neighbor node. For this reason,
the flooding method has no scalability. For example, OLSR [3]and AODV [4] are conventional MANET protocols that use
ID routing tables maintained by flooding. These protocols canonly be used in small networks. And, there is a gossip protocol[5] as a method similar to flooding. This protocol refrainsfrom transferring messages by probability. As a result, theamount of data transfer is reduced. However, this protocol can
not guarantee reachability of control messages to the wholearea. Therefore, it is not appropriate for inter mesh network.
Also, using a clustering technique can build a large network.
However, clustering is also difficult in vehicle wireless meshnetworks because the topology changes frequently.
So we use the Delaunay overlay network with the following
two features.
Delaunay overlay network can be constructed by control message exchanges between only close nodes.
• In the Delaunay overlay network, greedy routing basedon the location coordinate the destination node always
succeeds.
•

Because of these features, the Delaunay overlay network
always succeeds in routing even if the network becomeshuge. However, unlike the flooding network, each node in the
Delaunay overlay network does not know location coordinatesof other nodes in the network. Because, Dealunay overlay
netowork is constructed by close area control messages. By theway, since the node ID in the flooding use network is a network
locator, all nodes can know the locators of all nodes byflooding. Therefore, ID/locator resolution system is required
separately to get the location of destination mobile nodes.
Therefore, in this paper, we propose ID/Locator resolution
system using the structure of Skip Delaunay overlay network[6] (Top layer in Fig.1). Skip Delaunay overlay network is
a proposed overlay network structure to reduce the diameterof the Delaunay overlay network. We propose a protocol thatspreads node information on it. The node information is ID
and position coordinate pair. And, we also propose a protocolthat gets the diffused node information corresponding to thisnode information spreading protocol based on its node ID. In
this protocol, the transmission timing of node information iscontrolled to reduce the load on each link. In addition, thispaper abstracts low layer wireless networks. This is because
the Inter mesh network is oriented toward the best effort
network like the Internet.
In this paper, we use the following metrics to evaluate theproposed method.
•

Number of notification messages transferred per unit
time per node.

Proc. 33rd Int'l Conf. on Information Networking (ICOIN 2019),
pp.203-208, January 2019

Fig. 3. Environment assumed for the proposed system.

Fig. 4. Proposed system’s Network stack configuration.

Fig. 1. Structure of inter mesh networks.

networks interconnected by Delaunay overlay network nodes
with router functions.
B. Inter mesh network’s protocol stack

Fig. 2. Reachable range of network control messages.

Number of notification message stored per node.
Total number of messages transferred for ID/Locator
resolution.
This paper is organized as follows. Premise of this networkarchitecture and its related works are described in Section
II. The analytical framework and basic idea of the proposedsystem are described in Section III. Simulation evaluations
are described in Section IV, and conclusions are presented in
Section V.
••

II. P REMISE OF INTER MESH NETWORK ARCHITECTURE
AND ITS RELATED WORKSIn this section, we describe the framework of inter meshnetwork architecture. And, we described related works used
in inter mesh network architecture.
A. Environment of the proposed system
Fig. 3 shows the usage environment of inter mesh networkarchitecture. Structured overlay networks are more vulnerable
to malicious nodes than redundant flooding networks, theDelaunay overlay network is constructed with only trusted
vehicle nodes. Other nodes are used as local networks toconnect trusted nodes. Trusted nodes obtain their position
coordinates from GPS. In this paper, we assume wireless mesh

The assumed network stack of inter mesh network is shownin Fig. 4. The second layer from the bottom is a Delaunay
overlay network that uses a detour path with trusted nodes.
The bottom layer is constructed by local networks that connect
nodes in the Delaunay overlay network. A skip Delaunay
network is constructed on the Delaunay overlay network layerusing detour paths, and the proposed ID locator resolution
system is constructed in the skip Delaunay network layer. Low
layer communication is more efficient when the number oftransfers in the overlay network is reduced. This improves theoverall communication efficiency because the number of dataexchanges between layers is reduced, and processing in theoverlay layer is also reduced. In addition, skip Delaunay network reduces the diameter of the Delaunay overlay network.
The skip Delaunay network is used for message spreading in
the ID / locator resolution system. In the future, it will also
be used as a distributed database platform for applications.
C. Delaunay overlay network layer on other other wirelesscommunication systems
A Delaunay overlay network is a mobile ad-hoc network(MANET) protocol similar to the geographic position-assisted
routing proposed in a previous study [7]. In this system, we
use the overlay network as the overlay layer interconnecting
the wireless communication systems of the low layer. Delaunay overlay network has Delaunay graph topology using theposition coordinates of nodes. Therefore, greedy routing to
the location of the destination node always succeeds in thisnetwork. This protocol can construct a large-scale network
because it does not use flooding. Moreover, each node sends
control signals to maintain the network structure in a local
range. Basically each node of the Delaunay overlay network
creates routing tables to about 6 nodes. The middle of 2

Proc. 33rd Int'l Conf. on Information Networking (ICOIN 2019),
pp.203-208, January 2019indicates that the control messages reaches only around about
6 nodes when Delaunay overlay network is constructed.
Distributed construction method of Delaunay overlay network using detours [1] is applicable to the wireless link group
before networking. In this method, when there is no radio
link between two nodes that need to be connected, the detour
path is constructed by distributed method to replace the direct
overlay link. In this paper, this method constructs the Delaunay
overlay network and covers the wireless mesh layer. Then, themessage transfer in the overlay network layer is transmitted via
the wireless mesh network of the low layer. If the number offorwarding hops in the overlay network decreases, the numberof via mesh networks also decreases. For this reason, thereduction in the number of hops in the overlay network leads
to a reduction in the load on wireless mesh networks. In fig. 2,
The overlay network transfer indicated by the diagonal arrowis realized by the transfer in the wireless mesh network withthin arrows.
D. Skip Delaunay network layerThis proposed system is constructed using a skip Delaunay
network [6] that can be built on Delaunay overlay networks.
An example of skip Delaunay network is shown at the top
layer of Fig. 1. This network has shortcut links similar to Skip
Graphs [8]. In skip graphs, the node ID in rectangles also has
a role as a network locator. In the skip delaunay network,
since the node position is the network locator, the inside ofthis rectangle is the node position. Nodes are connected inorder of ID to construct a base network. This base network
is called Level 0 network. Each node has a random bit string
called Membership vector (MV), and generates shortcut links
based on the MV. The skip link sets of approximately 2Levelhop expected value length in Level 0 network. Level is an
integer equal to or greater than 0. (1/2)Level of the total node
to join in the Level sub-networks. The Level 0 network is theLevel 0 network wherein all nodes are joined. When a subnetwork Level increases by one, approximately one-half of thenodes are removed from the Level −1 sub-network. therefore,
the Level sub-network one-hop distance is approximately
2Level times longer than that of the Level 0 sub-network.
Skip delaunay network also creates a sub-network in thesame way, and there is a shortcut link of the length of
k Level (k is a constant ≒ 1.4) hops at Level 0. Originally,
this shortcut link is used to reduce the diameter of the network.
However, in this paper, we use this shortcut link for spreading
data to the whole network. Skip graphs are easy to apply
to the Delaunay overlay network because it is a method ofstacking sub-networks. In skip Delaunay network in Fig. 1,
sub-networks are stacked with the same structure. The rightof 2 indicates the routes of the locator notification messages
in this proposed method. The reachable range of messages
different from flooding is limited.
In addition, Hojo et al. [9] And Fujita [10] describe shortcut
link construction methods similar to Skip Delaunay network.

Fig. 5. One-hop notifications and acquisition by source nodes.

III. P ROPOSED ID/L OCATOR RESOLUTION SYSTEMOVERVIEWIn this section, we present an overview of the proposed
ID/Locator resolution system.
The proposed system has the following unique features.
• In this proposed method, membership vectors are generated from each node ID.
• This proposed method has messages spreading method.
• The proposed method has a method to get the locatorfrom arbitrary node ID by local search.
• The notification message transmission frequency iscontrolled. As a result, the load on each link is suppressed.
A. An outline of the proposed method
An outline of the proposed method is shown below.
In Fig. 5, a node vd broadcasts its locator notification
messages to the entire network. node vs sends a message tovd after obtaining the locator from vd ’s neighbors including
shortcut link neighbors. Note that vd has links to its neighbornodes based on skip Delaunay network rules. The thick arrows
in Fig. 5 represents sending notification messages on the skip
Delaunay network links. The number of hops at Level 0 toneighbors of each shortcut link is indicated by using k. In
many cases k is roughly 1.4. In the case where the node ispositioned linearly, it becomes the largest and the expectedvalue becomes 2. When k is 2, the load on the each link is
the largest. For this reason, after this section, the value of kis assumed to be 2.
In Fig. 5, vd sends locator notification messages to all Level
link neighbors. The Level notification frequency is set to
2Level unit time because, notification messages with many way
nodes increase the load on the way nodes significantly. Herethe number of nodes n increases; thus, number of messages
stored and transferred for each node is O(log n), where n is
the total number of nodes. Thus, this method is scalable.
Moreover, when each node receives locator information,
the locator notification message is obtained from surrounding
nodes based on the skip Delaunay network structure. Thus,
when a message arrives at its destination, there is that thedestination node is not already stay at the destination. In thiscase, additional locator information is obtained at the location
around has been reached. In this case, the message is closer
to the destination node; thus, it is possible to obtain additional
new locator information about the destination node. When thisProc. 33rd Int'l Conf. on Information Networking (ICOIN 2019),
pp.203-208, January 2019

Fig. 7.
Left side : Example of sending locator notification messages by a node. Right side : Notification message discovery mechanism in a skip Delaunay network.
Fig. 6. Sub-networks of repeated two split based on MVs.

occurs, the number of nodes is O(log n), where n is the total
number of nodes.
B. Locator notification mechanism for scalability
As whown in Fig. 6, all nodes in the skip Delaunay network
are bisected repeatedly to construct sub-network groups ofvarious sizes. In Fig. 6, ellipses represent node sets of subnetworks to which 1/1，1/2，1/4，1/8，1/16, . . . of allnodes belong. When two sub-networks are connected by aline, approximately one-half of the lower sub-network’s nodes
belong to the upper sub-network.
The white triangle is node d. When node d spreads its
locator, d sends locator notifications to one-hop neighbors
in each sub-network belonging to node d. In this case, thelocator notification is sent to more distant nodes in smaller
sub-networks. Note that most nodes in smaller sub-networks
receive notification messages. Thus, node s can find notification messages by searching smaller sub-networks. In Fig.6,
node s cannot find the node d locator messages in a large
sub-network. However, in the 101* sub-network, the node dlocator messages are delivered to node s. Thus, node s cansearch for locator information successfully.
We want to find a sub-network that belongs to node d using
its ID. Thus, in this system, unlike original skip Delaunay
network, its membership vector (MV) is generated using ahash function from its ID. In original skip Delaunay network,MVs are generated by randomly connecting 0 and 1 repeatedly.
In Fig. 6, node d’s MV = “101 . . . ” is generated from its ID
using a hash function. As a result, based on MV d is belong
to the following sub-networks based on the MV = “101 . . . ”
node d belongs to sub-networks “*”,“1*”,“10*” and “101*”.
An MV is defined as a bit sequence of infinite length. Therefore, an MV can generate length until a unique MV string.
Thus, node d can only belong to sub-network SN {d}. Notethat when the MV is increased by one order of magnitude, thesize of the MV sub-network will be reduced by 1/2. Therefore,
for n number of nodes, the number of sub-networks to which
node d belongs becomes O(log n). Therefore, this method isscalable, i.e., the number of nodes can be increased. If somenodes in a sub-network are checked, a node with an MV partany 1 bit is added to the sub-network MV is found. If this isrepeated, sub-networks with an MV can be identified quickly.

1) Amount of stored data by each node: Left side in
Fig. 7 shows node d neighbors in skip Delaunay network.
Node d sends locator notification messages to neighbor nodes(indicated by “1”) in each sub-network and receives locator
notification messages from those nodes. In the Delaunaygraph, each node has approximately six neighbors. Then, thenumber of sub-networks belonging to each node is O(log n).
Thus, each node receives O(log n) messages.
C. Notification messages discovery mechanism in the skip
Delaunay network
As shown in right side of Fig. 7, the node indicated by “2”is searching for a locator notification message spread by noded. The search behavior is described as follows. Search entity
is the subject executor of the search.
• In right side of Fig. 7, 101* sub-network is SN {d}.
• Node d’s MV can be obtained by inputting its ID to ahash function.
• An MV = 1* node in the * sub-network is discovered.
Then, the search entity is transferred to the node.
• An MV = 10* node in the 1* sub-network is discovered. Then, the search entity is transferred to the node.
• Similarly, MV = 101* nodes in the 10* sub-network
are discovered.
Then, the search entity is transferred to the node. The node
is a d. Thus, the d locator notification message is found andforwarded to the node that the search.
1) Number of nodes to be searched by the locator notification search mechanism: For n total number of nodes, thenumber of nodes searched by the notification message searchmechanism is described as follows. Several nodes are searched
in a single sub-network. Entity is transferred to a smaller subnetwork, Note that this process is repeated, and the maximum
number of repetitions is the maximum Level in the given
sub-network. Thus, in the worst case scenario, the numberof searches is O(log n).
D. Notification frequency adjustment for long-distance transmission load reduction
In the proposed method, a one-hop notification message istransferred in each sub-network. The transfer of the notification message is realized by multiple hops in the lower layer
networks. In other words, high Level one-hop notification

Proc. 33rd Int'l Conf. on Information Networking (ICOIN 2019),
pp.203-208, January 2019

Fig. 9. Search example of a node with arbitrary MV in a sub-network.
Fig. 8. Range of nodes that receive notification messages by vsmessages require many hops in lower layer networks, thus,
the load is increased. Therefore, we consider the loads of the
one-hop transfers in each Level to each node of the lower
layer networks. The transmission frequency of the highLevel notification messages in the proposed method is reduced
based on this consideration. The number of locator notification
messages passed through each node is reduced to O(log n) by
reducing the transmission frequency.
1) Consideration of notification message transfer count at
each node: When greedy routing is performed to gradually
reduce the remaining distance in the skip Delaunay network, nodes forward messages between the locator notification
message sending and receiving nodes. When a message istransferred to one-hop neighbors using a high Level link, themessage passes through many nodes in the lower layer.
The relationship between nodes is approximately symmetrical in the transmission of the locator notification message;
therefore, the total number of nodes through the notification
messages sent by a node is substantially equal to the numberof messages that arrive at the node. Furthermore, when thenode arrangement is extreme, in some cases, some nodes canreceive more messages than others. However, this case should
be addressed by local load distribution. Therefore, we do notconsider this case in this paper.
In Fig. 8, node vs and its neighbors are shown in the skip
Dealunay network constructed by n nodes. Here, vs roughly
belongs to a sub-network of the highest Level [log n]. Then,vs belongs to less sub-network, the number is approximately[log n]. When sending a message to a one-hop destination nodein the Level sub-network, the message is transferred via 2Level
nodes using the Level 0 sub-network. In Fig. 8, the reach of
the notifications in the Level are represented by the dottedlines and message icons. The number of nodes to receive
the message is also shown. The one-hop notifications of each
Level are received by 2Level nodes. In other words, O(log n)cannot be achieved. To address this problem, the proposed
method suppresses the notification transmission frequency andthe number of messages per unit time.
2) Suppressing notification message transmission frequency
per unit time: When, one notification message is sent per unit
time in Level 0, in other Levels, one notification message
is sent per 2Level unit time. Thus each Level number ofmessages will be per unit time average 1 message. Maximumof Level is O(log n). Therefore, the number of messages thatpass through vs per unit time becomes O(log n). This ensures
the scalability of the proposed method.
E. Behavior during search for a node with any MV in a subnetwork
When searching for a node with an arbitrary MV in thesubnetwork, the proposed system searches as in the example
below.
Fig. 9 is an example. Node A look up neighbor nodes having
MV = 1* from its database. However, node A cannot get. So,
A sends a neighbor discovery message to the closest known
node F (Arrow 1). Node F that received the message sends
own neighbor node list to node A(Arrow 2). If, Node A
find nodes having MV = 1* in the list, Node A sends search
entity to the node(Arrow 3). If, Node A can’t finde find nodes
having MV = 1* in the list, A sends a neighbor discovery
message to the 2nd closest known node. By the way, from thecharacteristics of MV, node A can find a target node with ahigh probability by examining a small number of nodes.
IV. B EHAVIOR CONFIRMATION AND EVALUATION BY
SIMULATION

We developed a Java-based simulator to examine the load ofthe entire network caused by broadcasting locator notification
messages. Moreover, we examined the number of transmission
hops for the ID/locator resolution in the given environment.
The initial state of the simulation is described as follows.
• The size of the simulation space is a 1.0 × 1.0.
• The simulation was performed while changing thenumber of nodes from 100 to 1000 in increments of100.
• Each node was assigned with position coordinatesaccording to a uniform distribution.
• The skip Delaunay network was constructed on thearranged node.
Under the above conditions, the change in load on each nodeassociated with the changing number of nodes was measured.
First, the number of times the locator notification messages
were transmitted was measured for each unit time at eachnode. Each node sends a locator notification message once
to each level neighbors in the skip Delaunay network. Thesemessages were transferred in the Level 0 Delaunay overlay
network by greedy routing. Each node counts the numberof times the notification message was transferred, and theaverage value was calculated. The high Level message was

Proc. 33rd Int'l Conf. on Information Networking (ICOIN 2019),
pp.203-208, January 2019

Fig. 10. Average and standard deviation of the number of messages received by each node.

Fig. 12. Message transfer for ID/Locator resolution Average value and standard deviation of the number of hops.

V. C ONCLUSION
In this paper, we have proposed an ID/locator resolution
system for a Delaunay overlay network using detour paths,
and we have confirmed the scalability of the mechanisms of
the system in simulations.

Fig. 11.
Average and standard deviation of the number of messages stored in each node.

also calculated when reducing the transmission frequency.
Specifically, (1/2)Level number of messages per unit time
were calculated. Fig. 10 shows the results. If uncontrolled,
the transfer count increased proportionally with the increasing
number of nodes. If the sending frequency was controlled,
the transfer count remained constant. In a flooding case, thenumber of messages passing through each node was the sameas the total number of nodes.
Next, the number of notification messages stored in eachnode was measured. Fig. 11 shows the results. Increases in
the number of stored messages were suppressed by increasing
the number of nodes. In a flooding case where all messages
were stored in each node, each node stored the same numberof messages as the total number of nodes.
Furthermore, we measured the total number of transmitted
messages used in the ID/Locator resolution. Here, all nodes
performed ID/Locator resolution for all nodes. Then, theaverage value was calculated. Fig. 12 shows the results. In
the skip Delaunay network, Increases in the number of hops
were suppressed by increasing the number of nodes. Onehop transfer in the skip Delaunay overlay network is realized
by Level 0 forwarding or underlay forwarding. Therefore, wemeasured the number of hops when this forwarding process
is realized in the Level 0 network. This case was more
proportional than the skip Delaunay network case. In addition,
in a flooding case where all messages were stored in eachnode, there was no need to search for messages.

ACKNOWLEDGEMENTS
This work was supported by JSPS KAKENHI Grant Numbers 16K12406. This work was supported by New Energy andIndustrial Technology Development Organization (NEDO).
The simulator used this study is based on the “Delaunay
overlay network configuration software implementation andmanagement tool software on communication links” fromthe National Institute of Information and Communications
Technology (NICT).
R EFERENCES[1] M. Ohnishi, M. Inoue, and H. Harai, “Incremental distributed construction method of delaunay overlay network on detour overlay paths,”
Journal of Information Processing, vol. 21, no. 2, pp. 216–224, 2013.
[2] Nankai Trough great earthquake countermeasure study workgroup,“About the countermeasure for the nankai trough great earthquake (thelast report),” 2013, http://www.bousai.go.jp/jishin/nankai/taisaku wg/ (inJapanese).
[3] T. Clausen and P. Jacquet, “Optimized link state routing protocol (OLSR),” Network Working Group RFC 3626, Oct. 2003,
http://www.ietf.org/rfc/rfc3626.txt.
[4] C. Perkins, E. Belding-Royer, and S. Das, “Ad hoc on-demand distancevector (AODV) routing,” Network Working Group RFC 3561, Jul. 2003,
http://www.ietf.org/rfc/rfc3561.txt.
[5] E. Leme, N. Ivaki, N. Laranjeiro, and R. Moraes, “Analyzing gossip
protocols for reliable manet applications,” in 2017 IEEE International
Conference on Edge Computing (EDGE), June 2017, pp. 98–105.
[6] S. Tsuboi, T. Oku, M. Ohnishi, and S. Ueshima, “Generating skip delaunay network for P2P geocasting,” in Proc. IEEE Creating, Connecting
and Collaborating through Computing (C5 2008). Poitiers, France:
IEEE, 2008, pp. 19–28.
[7] X. Hong, K. Xu, and M. Gerla, “Scalable routing protocols for mobile
ad hoc networks,” IEEE Networks, vol. 16, no. 4, pp. 11–21, 2002.
[8] J. Aspnes and G. Shah, “Skip graphs,” ACM Trans.
Algorithms, vol. 3, no. 4, Nov. 2007. [Online]. Available:
http://doi.acm.org/10.1145/1290672.1290674[9] M. Hojo, H. Nagao, T. Miyao, and K. Shudo, “A two-dimensional
structured overlay based on flexible routing tables,” in 2015 IEEE
Symposium on Computers and Communication (ISCC), July 2015, pp.
289–294.
[10] S. Fujita, “Hierarchical delaunay network for peer-to-peer overlay withaddress hashing,” in 2017 18th International Conference on Paralleland Distributed Computing, Applications and Technologies (PDCAT),Dec 2017, pp. 305–312.

Proc. 33rd Int'l Conf. on Information Networking (ICOIN 2019),
pp.203-208, January 2019