IEICE TRANS. ??, VOL.Exx–??, NO.xx XXXX 200x

1

PAPER

Special Section on New Technologies and their Applications of the Internet

A Decentralized VPN Service over Generalized Mobile
Ad-Hoc Networks
Sho FUJITA† , Keiichi SHIMA†† , Yojiro UO†† , Nonmembers, and Hiroshi ESAKI† , Member

SUMMARY
We present a decentralized VPN service thatcan be built over generalized mobile ad-hoc networks (Generalized MANETs), in which topologies can be represented as atime-varying directed multigraph. We address wireless ad-hoc
networks and overlay ad-hoc networks as instances of Generalized
MANETs. We ﬁrst propose an architecture to operate on various
kinds of networks through a single set of operations. Then, we
design and implement a decentralized VPN service on the proposed architecture. Through the development and operation of a
prototype system we implemented, we found that the proposedarchitecture makes the VPN service applicable to each instanceof Generalized MANETs, and that the VPN service makes it
possible for unmodiﬁed applications to operate on the networks.
key words: Network Architecture, Ad Hoc Network, Mobile
Computing1.

Introduction

There are many ways for mobile nodes to form a network. Some nodes search the Internet for other nodes
and form a network if the nodes can connect to access networks, which have diﬀerent characteristics anddiﬀerent coverages. Even if nodes cannot ﬁnd any access networks, the nodes can form ad-hoc networks bythemselves. The ad-hoc networks complement the access networks.
To maximize the time and quality of the communication among nodes, they can switch a network toanother to connect to. For example, there are nodes
that can connect to two diﬀerent kinds of access networks: WiFi networks and 3G cellular networks. If
a node can connect to either of them, the node canchoose the WiFi networks because they typically provide higher throughput. If a node cannot connect toany of the WiFi networks, the node can connect to the3G cellular networks. Even if some nodes cannot connect to any access networks, the nodes can use WiFi
to form an ad-hoc network.
However, some applications running on the mobile
nodes can cause problems even if the mobile nodes are
kept connected. This is because some application-levelinterfaces for communication are aﬀected when a mobile node switches a network to another. In what follows, we will see three problems caused in applicationlevel programming interfaces.
Manuscript received February 13, 2009.
The University of Tokyo††
Internet Initiative Japan†

Problem 1
The interface to transmit a packet to a destination nodeis aﬀected when its network address is changed. Sincetransport sessions using the old network address are invalidated, it is diﬃcult for the nodes to continue communicating.
Problem 2
The interface to transmit a packet to a group of nodes
is also aﬀected by the network setting among them.
When all of them are located in a single shared linksegment, they can use broadcast or link-local multicast addresses to deliver packets to all of them. Otherwise, they have to use multicast addresses with broader
scopes or adopt application speciﬁc mechanisms. Thatis, there is no consistent interface for group communication. Some autoconﬁguration protocols such as Dynamic Host Conﬁguration Protocol (DHCP) [1] andsome service discovery protocols such as Multicast Domain Name System (mDNS) [2] rely on the broadcast
or link-local multicast addresses; they do not work in a
network without a shared link segment.
Problem 3
The reachability to the mobile nodes is aﬀected. Some
subnetworks have limited reachability due to the lack ofglobal network addresses or a ﬁrewall or a network address translator (NAT) installed on the paths to them.
When a node moves to the subnetworks, the node becomes directly unreachable. The node need to implement additional procedure to ask other nodes to forward to packets to it.
To solve these issues, we present a decentralized
VPN service for a network of mobile nodes. As we will
describe in the later sections, we can generalize a network of mobile nodes as a generalized form of mobile
ad-hoc networks (Generalized MANETs). Generalized
MANETs include wireless ad-hoc networks and overlay
ad-hoc networks. Instead of solving the issues of the
networks separately, we propose an architecture thatallows us to operate on each instance of the Generalized MANETs through a single set of interfaces. Then,
we design and implement routing and forwarding mechanisms over the Generalized MANETs.
There have been studies on virtual private networks (VPNs), which hide the undesired characteristics

IEICE TRANS. ??, VOL.Exx–??, NO.xx XXXX 200x2

of link and network layers. As far as we know, however,they do not solve all of the following issues. First, theapplicability of some studies [3]–[6] is limited to networks where one or multiple nodes are reachable fromthe other nodes. It is diﬃcult to apply them to a network of mobile nodes. Second, some studies [7], [8] do
not provide neither a concept of group nor interfaces
for group communication.
The contributions of this paper are as follows.
• The proposed architecture allows us to work on
the topological properties of the networks; we canapply the same mechanisms to both wireless adhoc networks and overlay ad-hoc networks.
• The proposed VPN service is decentralized; oneor multiple nodes that are reachable from theother nodes are not mandatory but optional. This
makes the VPN service applicable to Generalized
MANETs.
The rest of this paper is organized as follows. In
section 2, we review two diﬀerent kinds of MANETs:
wireless ad-hoc networks and overlay ad-hoc networks.
In section 3, we ﬁrst propose an architecture that operate on each instance of Generalized MANETs through asingle set of interfaces. We then design a decentralized
VPN service on it. In section 4, we explain the implementation of a prototype system in detail. In section 6,
we discuss the issues we found thought the development
and operation of the prototype system. In section 7, we
review earlier studies on VPNs and compare them toours. In the last section, we present the future works
and summarize the research.
2.

Mobile Ad-Hoc Networks

In this paper, we consider mobile ad-hoc networks(MANETs) as networks with underlying links that do
not conform to three restrictions: bidirectionality, transitivity and stability [9]. This indicates that the linksof MANETs are not necessarily bidirectional nor transitive, and the availability and quality of the links varyin time. Since MANETs do not need to meet the above
restrictions, they allow the underlying links to be designed in a more ﬂexible way. On the other hand, higher
layer protocols need to handle the changes that takeplace in the underlying links. For example, they haveto handle network partition and merger.
In this section, we review two diﬀerent kinds of
MANETs, which have quite diﬀerent structures.
2.1

Wireless Ad-Hoc Networks

A wireless ad-hoc network consists of nodes loosely connected by wireless communication links. It has beenstudied in a lot of areas including inter-vehicle communication systems, where it is diﬃcult to use wired links
because each node moves, and communication systems

for disaster-stricken areas, where it is needed to build
communication infrastructure as soon as possible.
The wireless links do not meet the three restrictions in general. First, the communication range of thewireless links is aﬀected by propagation eﬀects and interference. Particularly, some propagation eﬀects, suchas multipath fading, and interference can take place locally, and may aﬀect only one of directions of links.
Therefore, wireless links can be unidirectional. Second,the communication range of the wireless links is limited
because of the propagation eﬀects. Even if Node 1 andNode 2 are in the communication range of Node 2 andNode 3, respectively, Node 1 is not necessarily in thatof Node 3. Therefore, wireless links are not necessarilytransitive. Third, the propagation eﬀects and interference vary in time, and thus the communication rangeof each node changes. This indicates that wireless links
are not stable.

1

3

1

1

move
3

2

3

2
(a)

3

Fig. 1

move
(b)

2

3

(c)

A wireless ad-hoc network

We can represent a topology of a wireless ad-hoc
network at some instant as a directed graph. Figure 1
illustrates an example of a time-varying network topology of a wireless ad-hoc network consisting of threenodes. For simplicity, we deﬁne the communication
range of each node as a ﬁxed-radius circles with thenode in the center; a node can deliver a message toother nodes that are inside the circle. Note that Node3 has a larger circle than the others in this example.
In Figure 1 (a), there are bidirectional links between
Node 1 and Node 2, Node 2 and Node 3. As Node 3
approaches to Node 1 in Figure 1 (b), a unidirectional
link from Node 3 to Node 1 becomes available because
Node 1 enters the circle of Node 3. In Figure 1 (c),the unidirectional link from Node 3 to Node 1 becomesbidirectional while the link between Node 3 to Node 2
becomes unavailable.
In wireless ad-hoc networks, we have a diﬀerent
interface to group communication; we cannot rely on
link-local broadcast to communicate with all of theother nodes. In Figure 1, the group of the nodes thatcan receive a message transmitted by Node 3 changes.
To transmit a message to all of the other nodes inwireless ad-hoc networks, we need another mechanism,
such as Simpliﬁed Multicast Forwarding (SMF) [10].
SMF in IPv6, however, uses site-local multicast addresses (ﬀx5::/16) instead of link-local multicast ad-

FUJITA et al.: A DECENTRALIZED VPN SERVICE OVER GENERALIZED MOBILE AD-HOC NETWORKS

3dresses (ﬀx2::/16) that some legacy applications are using. Consequently, we cannot support multicast functionality without modifying the applications.

1

3

4

move

2

3
(a)
open subnetwork

Overlays Ad-hoc Networks

3

1

3

1

2
2

2.2

1

1

4

2

3

2
(b)

3
1

3
4

2

(c)
firewalled subnetwork

Fig. 2 a time-varying network topology in an overlay ad-hoc
network

Some overlay networks have been used to support hostmobility in literature [3]–[6]. To keep mobile nodes
reachable, the nodes need to advertise their current network addresses to the other nodes. However, it is prohibited to advertise long preﬁxes in the core networkof the Internet to prevent the number of preﬁxes from
exploding. The nodes form an overlay network, whichis independent of the core network, and advertise theiraddresses over it. We call the overlay networks overlay
ad-hoc networks because they share some characteristics with wireless ad-hoc networks as we will see soon.
When a node moves from a network to another,
the network address of the node changes in general.
Until the node notify its new network address of othernodes, they cannot transmit a message to the node.
Therefore, the mobility of nodes changes the topology
of overlay ad-hoc networks. Moreover, the reachability
to the node might change if the underlying networks
have middleboxes such as NATs and ﬁrewalls, which
prevent bidirectional connectivity.
Figure 2 illustrates a time-varying network topology of an overlay ad-hoc network that consists of threenodes moving among four subnetworks. At the gatewayof Subnetwork 2 and Subnetwork 3, ﬁrewalls that block
all traﬃc initiated from the Internet are installed. In
Figure 2 (a), there is bidirectional connectivity among
all the nodes. Subsequently, Node 3 moves from Subnetwork 4 to Subnetwork 3 in Figure 2 (b). Node 1
and Node 2 cannot transmit a message to Node 3 because they do not know the new network address ofNode 3. On the other hand, Node 3 does know the network addresses of Node 1 and Node 2 and can transmit
messages to them although the message transmitted to
Node 2 does not arrive at Node 2 because of the ﬁrewall. Finally, Figure 2 (c) shows the state where Node 1
has received a message from Node 3. Now, Node 1 cantransmit a message to Node 3 because Node 1 knows
the network address of Node 3 and the ﬁrewall of Subnetwork 3 allows the replying message to the initiatedsession to pass. Therefore, Node 1 and Node 3 havea bidirectional link between them. As a whole, topologies of overlay ad-hoc networks at some instant are also
represented by time-varying directed graphs.
In overlay ad-hoc networks, we do not have generalinterfaces to group communication. For example, in
Mobile IP (MIP) [3], [4], link-local broadcast operates
on the link to which the node connects.

3.

Decentralized VPN Service over Generalized MANETs

As we have discussed in the previous section, wireless ad-hoc networks and overlay ad-hoc networks havecommon characteristics and issues. Instead of solving
their issues independently, in this section, we propose
an architecture that allows us to work on a generalized
form of MANETs. To this end, we discuss a networkmodel that fully represents topologies of MANETs including not only wireless ad-hoc networks and overlay
ad-hoc networks but also combinations of them. Then,
we deﬁne a set of common operations to work on the
network model. We call the architecture Generalized
MANET Architecture. Finally, we design and implement a decentralized VPN service on the architecture.
3.1

Generalized MANET Architecture

The purpose of the architecture is to decouple topological properties of MANETs from their implementation.
To describe the topological properties, we need a network model. So what is the network model that fully
represents generalized MANETs?
In the previous sections, topologies of both wireless ad-hoc networks and overlay ad-hoc networks are
represented by time-varying directed graphs. Combinations of them are also represented by them. We extend
these models to distinguish ways to communicate inGeneralized MANETs; their topologies are represented
by time-vary directed multigraphs.
So what kind of operations are needed to work on
Generalized MANETs? We deﬁne primitive operations
for unicast and multicast message delivery on the network model of time-varying directed multi-graph. As
we will argue in the later section, these two operations
are enough to implement some routing and forwarding mechanisms. The unicast message delivery is anoperation that delivers a message to the node’s neighboring node. And the multicast message delivery is
an operation that delivers a message to all the node’s
neighboring node.
The multicast message delivery is implemented differently in wireless ad-hoc networks and overlay ad-hoc
networks although the unicast message delivery is implemented in the same way. In wireless ad-hoc net-

IEICE TRANS. ??, VOL.Exx–??, NO.xx XXXX 200x

4

2
5
3

1
4

Fig. 3work

A multicast message delivery in a wireless ad-hoc net-

works, each node transmits a message to the link-local
multicast address once per its physical network interface.
Due to broadcast characteristics of wireless media,
the message are delivered to multiple nodes at the sametime. In Figure 3, we show a multicast message delivery
in a wireless ad-hoc network. A message transmitted
by Node 1 propagates as being degraded. The message
can be decoded at Node 2 and Node 3, but cannot be
decoded at Node 4 and Node 5 because of interference
and attenuation, respectively.

Neighbor
Table

ad-hoc networks are nodes that are registered in theneighbor table of the node and are reachable.
Nodes have to know about their neighboring nodes
to form overlay ad-hoc networks. We do not needto manually conﬁgure the neighboring nodes of each
nodes. Instead, nodes exchange its initial conﬁguration to its neighboring nodes and automatically ﬁll its
neighbor table. We call this process signaling.
Figure 5 illustrates a signaling process of threenodes. All the three nodes are originally connected tothe same network and share one another’s network addresses. In Figure 5(a), Node 1 and Node 3 have justmoved from the network to which Node 2 connects andgot new network addresses. So, they know the network
address of Node 2, while Node 2 does not know their
new network addresses. In Figure 5(b), Node 1 andNode 3 transmit a message to Node 2. Node 2 learns
their network addresses from the received message andthen adds them to its neighbor table. As we can see in
Figure 5 (c), Node 1 and Node 2, Node 3 and Node 2
can get bidirectional links respectively. Subsequently,
Node 2 advertises the contents of its neighbor table to
Node 1 and Node 3. Finally, Node 1 and Node 3 cancommunicate with each other through a bidirectional
link as we can see in Figure 5 (d).

2

2

2
5

1

3

2,3,4

3

3

move
1

1

1

3

1

2

2

3

4

2
open subnetwork

Fig. 4work

firewalled subnetwork

A multicast message delivery in an overlay ad-hoc net-

In overlay ad-hoc networks, the multicast message
delivery is implemented as follows. A node looks up
its neighbor table to get the network addresses of theneighboring nodes and then transmit a message to eachof the network addresses in unicast. The neighbor table
is a small database of the node’s neighboring node. It
is maintained by a process called signaling, as we will
see later.
In Figure 4, we show a multicast message delivery
in an overlay ad-hoc network. Node 1 tries to transmit
a message in unicast to the three network addresses
got from its neighbor table. Although the messages
sent to Node 2 and Node 3 are successfully delivered,the message sent to Node 4 is not delivered becauseof the ﬁrewall installed in the Subnetwork that Node
4 belongs to. Therefore, neighboring nodes in overlay

(b)

1,3

1,3

2

2

123

123

1

3

1

2

2,3

2
(c)

Fig. 5

2

(a)

3
1,2
(d)

signaling process in overlay ad-hoc networks

The multicast message delivery in overlay ad-hoc
networks depends on network address of some nodes.
If the node cannot connect to them, it cannot continue
operating. By contrast, the multicast message delivery
in wireless ad-hoc networks does not. As we have seenin Figure 5 (a), due to the multicast message delivery inFUJITA et al.: A DECENTRALIZED VPN SERVICE OVER GENERALIZED MOBILE AD-HOC NETWORKS

5

wireless ad-hoc networks, Node 1 and Node 3 know the
network address of Node 2. And the network address
allows them to initiate the signaling process. Therefore, it is true that nodes that are reachable from theother nodes are helpful, but they are no more mandatory but optional; Generalized MANETs can be formed
in a decentralized fashion.
3.2

Routing and Forwarding on Generalized MANETs

We assume that each node has a unique identiﬁer. We
make a L2 VPN service from the primitive operations
provided by Generalized MANETs architecture.
The functions needed to achieve a L2 VPN service
are to encapsulate L2 frames, to deliver the encapsulated L2 frames to the node speciﬁed with the identiﬁer of the L2 frame, and to deliver the encapsulated
L2 frames to all the nodes in the Generalized MANET.
We cannot assure the delivery of the encapsulated L2
frames because the Generalized MANET might be partitioned. The virtual link segment provided by the service can be used as if it is an Ethernet-like shared linksegment, because the L2 frames, including the TTL
ﬁeld of IPv4 and the hop limit ﬁeld of IPv6, are not
modiﬁed during the delivery.
We need to design routing and forwarding mechanisms speciﬁc to General MANETs. Static routing
and centralized routing scheme are not applicable toGeneral MANETs because the network topologies varyin time and can be partitioned. Moreover, we need tohandle unidirectional links.
We reuse routing and forwarding mechanisms thatare designed for wireless ad-hoc networks in this paper. The mechanisms should work correctly on Generalized MANETs because assumptions they rely on is
the same as that of Generalized MANETs. Particularly,
we implemented DYnamic MANET On-demand routing (DYMO) [11] and SMF on Generalized MANET
architecture. We will address the implementations in
the later section.
4.

Prototype Implementation and Evaluation

formed over MANETs. We can run unmodiﬁed applications on them since the virtual network interfaces
support the same operations as Ethernet network interfaces. the virtual network interfaces are always activated and can keep their conﬁgurations because thevirtual network interfaces are independent of the physical network interfaces. And thus they can keep sessionsof transport and application layers.
The virtual network interfaces are implemented
with a TAP device. The TAP device provides a pair ofa virtual network interface and the corresponding ﬁledescriptor. If applications transmit a L2 frame fromthe virtual network interface, the middleware can readit from the ﬁle descriptor as a byte stream. And if
the middleware writes a byte stream to the ﬁle descriptor, the applications can receive it through the virtual
network interface as a L2 frame. It connects the operating system and the middleware where we implemented
the proposed architecture and routing and forwarding
mechanisms running on the architecture. In Figure 6,
we show the structure of the prototype system.

MANET
Protocols
TCP/IP
Applications(1)

Operating System

Fig. 6(3)
PHY IFACE

The software architecture of the prototype system

In Figure 7, we show the frame formats used whenthe middleware transmit frames from the physical network interfaces. Figure 7 (a) depicts the format for thecontrol plane such as signaling and routing. Figure 7(b) depicts the format for the data plane to deliver L2frames.
Ethernet Header

Ethernet Header

IP Header

IP Header

UDP Header

UDP Header

MANET Control

MANET Encap Data
Ethernet Frame

Implementation

We implement a middleware based on the proposed architecture. The middleware provides virtual network
interfaces; each of them corresponds to a virtual link

(2)

TAP IFACE

We implemented a prototype system of the decentralized VPN service over generalized MANETs. The prototype system is based on our two previous works: An
Overlay Mobile ad-hoc Network at the edge of the Internet (OMNI) [12] and A middleware for Transparent
MObile ad-hoc networking Systems (ATMOS) [13]. In
this section, we describe the implementation of the prototype system and then evaluate the prototype system.
4.1

Generalized MANET
Architecture
FDESC
SOCK

(a)

Fig. 7(b)

The message formats used in the prototype system

The middleware transmits all the messages

IEICE TRANS. ??, VOL.Exx–??, NO.xx XXXX 200x

6

through two functions: unicast send in Figure 8 andmulticast send in Figure 9, which implement unicast
and multicast delivery in Generalized MANETs, respectively. And the middleware receives all the messages through the function: receive in Figure 10. We
address the implementations of the functions.
procedure unicast send(msg, addr)
encapsulate(msg)
sendto(sock, msg, addr)

Fig. 8Process in Transmitting Unicast Message

In Figure 8, we show the pseudocode of the unicast send function. It accepts arguments of a message
to send and information of a neighboring node to which
the message is sent. It transmits the message to the network address of the neighboring node through a UDP
socket after encapsulating the message.
procedure multicast send(msg)
encapsulate(msg)for each neigh ∈ neighbor table.get()do sendto(sock, msg, neigh.addr)
for each if ace ∈ physical if aces
do sendto(msg, M CAST ADDR)

Fig. 9Process in Transmitting Multicast Message

In Figure 9, we show the pseudocode of multicast send function. It accepts only an argument of amessage to send. It ﬁrst encapsulates the message. In
the ﬁrst loop, it transmits the message to each of its
neighboring nodes in unicast. This loop implements
multicast delivery for an overlay ad-hoc network ofGeneralized MANET. In the second loop, it transmits
the message to the link-local multicast network addressfrom each of the physical network interfaces. This loop
implements multicast delivery for a wireless ad-hoc network of Generalized MANET.
procedure receive(msg, neigh)if not included(neigh.addr, f f x2 :: /16)
then neighbor table.update(neigh)if destine to this(msg)then write(tap, decapsulate(msg))
if is broadcast(msg)then handle multicast(msg, neigh)else handle unicast(msg, neigh)Fig. 10Process in Receiving Message

In Figure 10, we show a pseudocode of receivefunction, which is used to receive a message sent by
unicast send and multicast send functions. It ﬁrst

checks if the message is sent with the link-local network addresses. If not, it adds the information of theneighboring node to its neighbor table. Subsequently, it
checks if the message is destined to itself. If so, it writes
the message to the tap ﬁle descriptor. Finally, the message is handled based on a group bit in the destination
MAC address. If the group bit is set, the message isprocessed to be transmitted in multicast. Otherwise,
the message is processed to be transmitted in unicast.
In this prototype system, we implement DYMO
and SMF for unicast routing and multicast forwarding,respectively. Both of them are originally designed for
wireless ad-hoc networks. We replace the native operations, such as multicasting with the link-local multicast
addresses, with the Generalized MANET primitive operations to make DYMO and SMF applicable to Generalized MANETs including overlay ad-hoc networks aswell as wireless ad-hoc networks.
4.2

Evaluation

We conduct an experiment to verify that our prototype
system can form a VPN over a Generalized MANET
and solve the three problems we mentioned earlier.
To this end, we build a network and switch its
settings between those illustrated in Figure 11 (a) and
Figure 11 (b). In Figure 11 (a), Node 1 and Node 2 areconnected by a wireless link, and they form an wirelessad-hoc network.
Node 2, Node 3 and Node 4 areconnected to the Internet and form an overlay ad-hoc
network. Since we add information of Node 3 to theneighbor tables of Node 2 and Node 4, Node 2, Node
3 and Node 4 can establish bidirectional connections inthe same way as we have seen in Figure 5. In Figure
11 (b), Node 4, which activates its wireless network interface and leaves the Internet, is connected to Node 1
by a wireless link. Note that, in both of the network
settings, Node 1, Node 2 and Node 4 are sharing theirwireless conﬁgurations. Since their wireless network interfaces have only IPv6 link-local addresses, any pairsof them can communicate if and only if they are within
the communication ranges of each other.
Since the virtual links of the nodes are activated all
the time, their network addresses are always available.
Hence, Problem 1 is solved. Moreover, broadcast andlink-local multicast network addresses are also always
available. Hence, Problem 2 is also solved. When Node1 tries to transmit a frame to Node 4 via the virtual link,a mechanism implementing DYMO starts establishing aroute between them. Node 1 initiates ﬂooding a RREQ
message to advertise its network address and searchfor Node 4. Node 4, or possibly the nodes that havevalid routing entry for Node 4, reply to the RREQ
message with a RREP message to advertise its network
address. Since these processes are implemented using
the unicast send and multicast send, DYMO canwork well on the Generalized MANET. We conﬁrmed

FUJITA et al.: A DECENTRALIZED VPN SERVICE OVER GENERALIZED MOBILE AD-HOC NETWORKS

7

that Node 1 and Node 4 could continue communicatingwith each other while we switched the network setting.
We also conﬁrmed that packets destined to broadcast
and link-local multicast addresses were delivered to theother node. Hence, Problem 3 is also solved.

3

4

1

4

2
move

(a)
3

4

1

4

2
move

(b)

Fig. 11

5.

Providing a VPN service over a Generalized MANET

Discussion of Logical Grouping

In this section, we consider a network design strategy
assuming the proposed VPN service.
In the early days of the Internet, nodes were unlikely to move from a physical link segment to another; nodes were assigned to the physical link segments. These physical segments were useful to deal
with groups of nodes. The reason is the following.
First, the physical link segments provide boundaries
of access control. Since nodes that do not share thesame link segment cannot communicate directly, it iseasy to enforce some communication policies at middleboxes such as routers. Second, the physical linksegments provide intuitive group communication, linklocal broadcast.
Since nodes move from a physical link to another inthe current Internet, these beneﬁts of the physical links
are no longer available. We need to ﬁnd alternativesof the physical links. The decentralized VPNs havealready provided intuitive group communication, whichis independent of the network structure. If we add somemechanisms for access control, the decentralized VPNs
can be on behalf of the physical link segments in thecurrent Internet.

6.

Related Works

In this section, we review the earlier studies related tothis paper.
Virtual Private Network (VPN) [14]–[17] is a technique that enables a host to connect to a remote linkor network by encapsulating a L2 frame or L3 datagram with other protocol headers. The virtual links
or point-to-point links provided by these techniques are
not only similar to logical links but also conforming
to most of their requirements. However, Although thegoal of VPNs is to extend links or networks that arelocated in remote places, our architecture aims at providing persistent views of link structures to higher layers. Therefore, logical links are relevant even if there
are no connections to other hosts, while virtual links of
VPNs are disabled in the same situation in general.
As we have discussed the mobility support in theInternet, the idea of a separation between physical andlogical links is similar to a separation between locatorsand identiﬁers that appears in some protocols such as
Mobile IP (MIP) [3], [4], ROAM [5], [6], Host Identity
Protocol (HIP) [7], and Location Independent Networking for IPv6 (LIN6) [8]. Although both of the separations share ideas to some extent, we argue that a separation between locators and identiﬁers is not enoughfor some applications to run without any modiﬁcations
on the Mobile Internet. If we modify these protocols
slightly to adjust them to our architecture, their techniques for encapsulating a frame or datagram and/or
signaling a mobility can be utilized. An architecture
proposed to separate network preﬁxes between core andedge networks [18] is also similar to our architecture.
We have not discussed the architectural considerationof core networks.
We have implemented a prototype system thatbuilds ﬂat, logical links over MANETs. This is similar to IEEE 802.11s, which is an extension amendmentof the IEEE 802.11 protocol and build ﬂat Ethernet segments over wireless multi-hop networks, and a proposalthat builds virtual links over MANETs [19]. Althoughthese works are focusing on MANET environments andespecially IEEE 802.11s can be applied only to IEEE
802.11 protocol family, our proposed architecture can
support the environment of the mobile Internet too.
7.

Conclusion

In this paper, we presented a decentralized VPN service
over generalized MANETs. The proposed service consists of two parts: an architecture that provides a setof common operations to generalized MANETs and amechanism to route and forward L2 frames using these
operations. The purpose of the architecture is to decouple the topological properties of the networks from theirimplementation. It allows us to solve the issues that

IEICE TRANS. ??, VOL.Exx–??, NO.xx XXXX 200x

8

comes from the topological properties without reinventing solutions for each instance of generalized MANETs
independently. And then, we demonstrated that we canport routing and forwarding mechanisms designed for
wireless ad-hoc networks to the proposed architectureand give them broader applicability. Through the development and operation of the prototype system, wefound that we can form a VPN over a network thatconsists of wireless ad-hoc networks and overlay ad-hoc
networks and that some unmodiﬁed applications run
on the VPN service despite changes of the underlying
networks structures.
Acknowledgement

and G. Zorn and B. Palter, “Layer Two Tunneling Protocol ”L2TP”,” Network Working Group RFC 2661, August
1999.
[16] Y. Tobioka, N. Mimura, H. Morikawa, and T. Aoyama,“Mynetspace:a user controlled virtual closed network for
ﬂexible access control,” IEICE Tech. Rep., pp.139–144,
March 2005.
[17] S. Miyakawa, S. Ono, T. Kubo, K. Terao, and K. Hasebe,“Yet Another Mobility Support for the Internet,” IEIEC
Transactions on Information and Systems, vol.E82-D, no.4,
pp.778–783, April 1999.
[18] D. Jen, M. Meisel, L. Wang, B. Zhang, and L. Zhang, “Towards A New Internet Routing Architecture: Arguments
for Separating Edges from Transit Core,” ACM Workshop
on Hot Topics in Networks, October 2008.
[19] F. Templin, “MANET Autoconﬁguration over Virtual Ethernets,” Work in Progress, February 2007. draft-templinautoconf-virtual-00.

Special Thanks to Kaoru Yoshida and Sergio Carrilho,
who reviewed the early version of this paper and provided relevant feedbacks.
References[1] R. Droms, “Dynamic Host Conﬁguration Protocol,” Network Working Group RFC 2131, March 1997.
[2] S. Cheshire and M. Krochmal, “Multicast DNS,” Working in Progress, September 2008. draft-cheshire-dnsextmulticastdns-07.txt.
[3] C. Perkins, “IP Mobility Support for IPv4,” Network
Wokring Group RFC 3344, August 2002.
[4] D. Johnson and C. Perkins and J. Arkko, “Mobility Support
in IPv6,” Network Working Group RFC 3775, June 2004.
[5] I. Stoica, D. Adkins, S. Zhuang, S. Shenker, and S. Surana,“Internet Indirection Infrastructure,” ACM SIGCOMM,
2002.
[6] S. Zhuang, K. Lai, I. Stoica, R. Katz, and S. Shenker,“Host Mobility Using an Internet Indirection Infrastructure,” ACM/USENIX Mobisys, 2003.
[7] R. Moskowitz and P. Nikander and P. Jokela and T. Henderson, “Host Identity Protocol,” Network Working GroupRFC 5201, April 2008.
[8] M. Kunishi, M. Ishiyama, K. Uehara, H. Esaki, and
F. Teraoka, “LIN6: A New Approach to Mobility Support in IPv6,” International Sympsium on Wireless Personal Multimedia Communications, September 2001.
[9] I. Chakeres, J. Macker, and T. Clausen, “Mobile Ad hoc
Network Architecture,” Work in Progress, November 2007.
draft-ietf-autoconf-manetarch-07.
[10] J. Macker and S.D. Team, “Simpliﬁed Multicast Forwardingfor MANET,” Working in Progress, November 2008. draftietf-manet-smf-08.
[11] I. Chakeres and C. Perkins, “Dynamic MANET On-demand(DYMO) Routing,” Work in Progress, February 2008.
draft-ietf-manet-dymo-12.
[12] S. Fujita and H. Esaki, “OMNI: an Overlay Mobile ad-hoc
Network at the edge of the Internet,” International Conference on Future Internet Technologies, June 2008.
[13] S. Fujita and H. Esaki, “ATMOS: A middleware for Transparent MObile ad-hoc networking Systems,” International
Conference on Ubiquitous Information Management andCommunication, January 2009.
[14] K. Hamzeh and G. Pall and W. Verthein and J. Taarud and
W. Little and G. Zorn, “Point-to-Point Tunneling Protocol(PPTP),” Network Working Group RFC 2637, July 1999.
[15] W. Townsley and A. Valencia and A. Rubens and G. Pall

Sho Fujita
received his B.E. and M.E.
degrees from the University of Tokyo,
Tokyo, Japan in 2004 and 2006, respectively. He is currently a ph.D. candidate
at Department of Information Communication and Engineering, Graduate Schoolof Science and Technology, the Universityof Tokyo. His research interests are in mobile ad-hoc networks and network mobility.

Keiichi Shimareceived his Ph.D degree in Graduate School of Information
Science at Nara Instisute of Science andTechnology in 2009. He is now a senior researcher at Internet Initiative Japan Inc.
His interests is next generation Internet,
mobility and ad-hoc networking technologies.

Yojiro Uo
received his Ph.D degree in
Graduate School of Information Scienceat Japan Advanced Instisute of Scienceand Technology in 2003. He is a seniorresearcher at Internet Initiative Japan Inc
since 2002. His main research area is interaction technologies between real worldand network space and next generation
Internet.

FUJITA et al.: A DECENTRALIZED VPN SERVICE OVER GENERALIZED MOBILE AD-HOC NETWORKS

9Hiroshi Esaki
received the B.E. and
M.E. degrees from Kyushu University,
Fukuoka, Japan, in 1985 and 1987, respectively. And, he received Ph.D from University of Tokyo, Japan, in 1998. In 1987,
he joined Research and Development Center, Toshiba Corporeation, where he engaged in the research of ATM systems.
From 1990 to 1991, he has been at Applied Research Laboratory of Bellcore
Inc., New Jersey (USA), as a residential
researcher. From 1994 to 1996, he has been at CTR (Center
for Telecommunication Research) of Columbia University in New
York (USA). During his staying at Columbia University, he has
proposed the CSR architecture, that is the origin of MPLS(MultiProtocol Label Switching), to the IETF and to the ATM Forum.
From 1996 to 1998, he has conducted the CSR project in Toshiba,
as a chief architect. Since 1998, he has served as a professor at the
University of Tokyo, and as a board member of WIDE Project(www.wide.ad.jp). He is a fellow of IPv6 Forum, a vice presidentof JPNIC and a Board of Trustee for ISOC (Internet Society).