第 XXIV 部
Integrated Distributed
Environment
with Overlay Network
W
I
D
E
P
R
O
J
E
C
T
第 24 部
Integrated Distributed Environment with Overlay Network
Location and routing may be done in the
same procedure because it may be necessary
第 1 章 IDEON: Integrated Distributed Environment
to traverse the topology of the network to
with Overlay Network
locate the peer.
Autonomous routing may
involve creation of topology in an ad-hoc
manner.
Rendezvous, Location and Routing
IDEON (Integrated Distributed Environment
We would like to propose alternative networking
designs so that each of these can be performed in
unrestrained and imaginative ways.
with Overlay Network) is a working group that
By “unrestrained and imaginative” we mean
pursues autonomy in the designs of distributed
that no restraint should be made by the network
systems.
as to which object can become the target for com-
We believe that network designs should encour-
munication, without intervention of any author-
age self-generation of activities which utilize
ities or privileged intermediate nodes, and that
resources spread over different locations (hence,
new ways of communication can be developed by
integrated distributed environment) by allowing
the creativities of the participants of the network.
spontaneous creation of layers of abstract network
Putting more stress on autonomy changes how
the three ingredients of communication are per-
Since autonomy implies that there is no authority to guarantee the truthfulness of information
(or that such an authority is weak), trust becomes
In the IDEON working group we produced
meeting place. In computer communications,
four major research outputs. Youki Kadobayashi
such a meeting place can be a name space or
extends Kademlia algorithm, Kenji Saito works on
a space for identifiers. Rendezvous performed
trust management and its applications, Takaaki
under autonomy may allow spontaneous nam-
Ishida made a simulator for spatially sticky infor-
ing and resolution among the participating
mation distribution algorithm for RF communica-
nodes themselves.
tion, and Yusuke Doi introduced bloom filters to
enable peer group management on DHT.
This is to locate the node that represents the
The research by Youki Kadobayashi contributes
identifier. The node is typically identified by
for heterogeneous structures of DHT network-
the identifier in the lower layer of the network.
ing.
Autonomous location may involve identifying
enables fair-sharing between nodes that have dif-
the closest copy of information among redun-
ferent capabilities like connection bandwidth, pro-
dant copies spread over the network with help
cessor power, and storage capacity.
from participating nodes in vicinity.
3. Routing (or how to reach the peer)
Youki’s extension on Kademlia algorithm
To accomplish high-availability and robustness
at the same time, heterogeneous networking is
This is to traverse the topology of the net-
a rational approach. With the Youki-Kademlia
work so that a message can reach the peer.
we can integrate various devices like refrigerator,
353
Integrated Distributed Environment with Overlay Network
1.2 Summary of the Research
The word “rendezvous” means a prearranged
2. Location (or how to locate the peer)
24
an important issue.
formed:
1. Rendezvous (or how to identify the peer)
●第 部
over the IP layer (hence, with overlay network ).
24
1.1 Toward Unrestrained and Imaginative
w
●第 24 部 Integrated Distributed Environment with Overlay Network
HDD video recorder and many more massive
mechanism.
always-on devices into the DHT network. Inte-
groups (resource groups of peer nodes) gathered
grated with greater devices like server comput-
on peer’s characteristic is fine-grained set of peers
ers, these devices may introduce a good amount
that have the characteristics.
of proximity and redundancy.
This research is described in detail in chapter
This research is described in detail in chapter
“Achieving Heterogeneity and Fairness in Kademlia.”
“Peer Group Rendezvous with DHT.”
Another work jointly done by those members is
The research by Kenji Saito is on trust man-
tructure. The pointer notation is called Uniform
agement. Kenji is trying to apply the i-WAT sys-
Rendezvous Pointer (in short, URP). The most
tem to many applications including decentralized
significant difference between regular URL/URI
systems like Jabber (coupled with PGP identity),
and URP is that URP does not just identify
and web-based systems for WIDE project research
a resource.
community or for readers of a book.
a client should try to search among overlays and
Instead, URP is a notation how
n
system to work correctly.
And the research
Because resources on some overlays like Freenet
n
is a building block that could be applied by
and Gnutella is unstable and has no identity, nei-
a
many decentralized systems like DHT, file shar-
ther just an identifier nor locator would suffice
3
ing/caching, and sensor networks. The next step
in inter-overlays. URP would be an efficient glue
0
how the result would be verified and treated.
would be integrating between one or more DHT
between an i-WAT overlay network and other col-
0
Spontaneous contribution helps decentralized
algorithms and barter transactions that i-WAT
laborative overlay networks.
2
u
a
l
r
e
p
r
about pointer on an inter-overlay network infras-
o
t
For example, intersection of peer
expects.
“Uniform Rendezvous Pointer.”
“i-WAT: The Internet WAT System.”
E
J
Takaaki’s work realizes spatially sticky informa-
To realize the communication model IDEON-
O
tion between RF-transmitter devices using a very
wg proposes, we still have many open issues to be
R
1.3 Open Issues
The research of Takaaki Ishida is unique.
simple algorithm. A simulator is made to inves-
solved. To foresee the next steps of our research,
P
C
T
This research is described in detail in chapter
This research is described in detail in chapter
tigate how the algorithm works on random traffic
we describe those issues here.
E
patterns. His vision of applications includes ad1.3.1 Measurement and Visualization
D
hoc advertisement and event notification in spe-
Measurement is always needed to keep a system
W
I
cific locations.
This research is described in detail in chapter
“Design of Content Cruising System.”
well-formed and stable. For example, active DDoS
should be detected quickly after the attack begun
The research by Yusuke Doi enables peer groups
and blocked to prevent other normal traffic to fail.
managed on a DHT network to be used as the
Visualization is also needed to make measurement
foundation of fine-grained node discovery. The
understandable by human administrators.
work introduces a protocol to take intersection
But, measurement is always difficult for true
between sets managed on different nodes. It uses
distributed systems. IDEON expects all the sys-
bloom filters effectively and reduces network traf-
tems have enough freeness. To ensure freeness, no
fic at risk of false positives.
central management point should be exist in the
With such an effective way to get intersection,
system.
a properly managed index of resources on DHT
Two evident examples are closely related with
can be made into an effective resource discovery
IDEON activity. One is DHT and the other is
354
W
i-WAT.
Those two are both true distributed,
without authority nor checkpoint to pass.
A DHT system may have some shared seeding nodes.
I
D
E
P
R
O
J
E
C
T
But at the same time, a user who wants application beyond the framework needs to modify the
framework or to create a new and suitable frame-
Like root servers of DNS, the sys-
work for the application. One outstanding exam-
tem may mandate a node to contact some set of
ple of SU overlay network is Project JXTA (see
nodes before joining into the DHT network. With
http://www.jxta.org/).
these seeding nodes, the system can take some
sort of statistics and control. But this kind of
checkpoint may put bottleneck on the system and
1.3.3 Update and Transition Process
Architectures
of
overlay
networks
should
most systems would take different approach. Pos-
include remote update functionality. An overlay
sible approaches for DHT may be like random-
network is actually a coordination of programs on
sampling, automatic aggregation like aguri, and
many nodes. This is totally distributed architec-
active event transmission over the overlays.
ture thus update of the programs is not easy as
For i-WAT and other PGP-like systems, mea-
update of server centric service. Moreover, tran-
surement is a more difficult issue. Communication
sition from old network to new network would
model of those systems is truly ad-hoc peer-to-
be a challenge like re-numbering of IP-network or
peer and no one other than the two communicat-
transition from IPv4-only world to dual stacked
ing now can tell when and how the communication
world with IPv6.
occurs. Difficulties may arise more if there is no
daemonic node to process request except a user’s
(on later version more discussion would be
here.)
jabber client (i-WAT case). In this case, there is
with
(PG)3 A
Working
Group
the net.
(PG)3 A stands for PGP/GnuPG Applications,
We must investigate and select among the two
evident architectures, multi thin (MT) overlay
and the working group has been studying new
trust mechanisms for distributed autonomous systems based on peer-to-peer authentications.
network and single ultimate (SU) overlay network.
Since its activities are technically no longer
The goodness of MT overlay network is its extend-
bounded to usage of PGP, and the subject mat-
ability. For each new application and objectives,
ter is closely related to many research topics in
one can create its own overlay network that has
IDEON, the two working groups are going to be
tailored naming and routing system most suitable
united to form a single group to pursue autonomy
for the application.
in distributed environments.
At the same time, MT overlay introduces com-
This section describes the past activities of
plexity. If there is no interconnection between
(PG)3 A and the prospects of activities in IDEON
each MT overlay that would be inconvenient. The
in the future with respect to trust in distributed
resources on the overlay cannot be accessed from
autonomous systems.
outside of the overlay. To overcome its restriction,
one or some set of syndication mechanism would
be needed.
Pros and cons of SU overlay network is just vice
1.4.1 Brief History of (PG)3 A
(PG)3 A was established in October 2002. While
its goal was deployment of PGP through devel-
SU overlay introduces widely-applicable
opment of PGP/GnuPG applications, its activi-
naming and routing framework, thus most of
ties were focused on development of a new trust
application would be okay under the framework.
mechanism based on peer-to-peer authentication,
versa.
355
Integrated Distributed Environment with Overlay Network
1.3.2 Multi Thin vs. Single Ultimate
24
24
1.4 Integration
●第 部
no way to take measurement if the user is not on
w
●第 24 部 Integrated Distributed Environment with Overlay Network
using a sort of currency system to facilitate
most interested when those strategies and pay-
exchanges.
ments are about barter relationships, connecting
The following experiments have been conducted
by (PG)3 A.
directly the parties of exchanges. The medium
of such exchanges can be seen as a barter cur-
application of PGP (WIDE Camp March
application of barter currencies to formation of
2003)
distributed autonomous systems.
i-WAT was introduced in this experiment.
The objective was to evaluate the Jabber-
o
t
rency. One direction that IDEON can pursue is
r
1. Evaluation of a free currency system as an
based i-WAT system.
第 2 章 Achieving Heterogeneity and Fairness in
p
Only seven partici-
Kademlia
e
pants could experience actual transactions,
r
and the important finding was that even peo-
n
Attempts to construct overlay networks in ubiq-
2. Verification of a cooperation mechanism using
uitous networked environments will face chal-
n
a
Abstract
a free currency (WIDE Camp September
lenges of both performance and resource hetero-
a
the introduction of OMELETS below.
2003)
geneity. We describe enhancements to Kadem-
3
the key exchange cumbersome. That led to
u
l
ple with sufficient knowledge of PGP found
OMELETS (Open, Modular and Extensi-
lia, a peer-to-peer system which has provable
0
environment. Our enhancements can accommo-
was implemented as a web application using
date nodes with arbitrary degree of heterogene-
OMELETS. 166 WIDE members have been
ity, while at the same time ensuring fairness,
using WIDE Hour, and we are beginning
without adding much overhead. A probabilistic
to learn a lot about free currency exchange
mechanism to check parameter integrity is intro-
through the experiences.
duced, which in turn is exploited to probabilis-
C
T
ment. A currency system called WIDE Hour
2
consistency and performance in a fault-prone
E
ble LETS ) was introduced in this experi-
J
0
1
1.4.2 Future of IDEON and Trust
approach, we have implemented a prototype and
mic mechanism design (DAMD) shows that
then evaluated its ability to accommodate arbi-
researchers of distributed systems are begin-
trary degree of heterogeneity.
in
D
E
interests
distributed
parameters. To demonstrate the feasibility of this
algorith-
Recent
P
R
O
tically check compliance of nodes to advertised
W
I
ning to pay more attention to incentives for
cooperation and fairness of sharing resources.
2.1 Introduction
DAMD is a unified effort between economics
Many DHT algorithms[171, 237, 271] assume
(mechanism design part) and computer science
that all participating nodes have comparable
(distributed algorithmic part). It is characterized
amount of resources, and that they can accom-
by presence of strategies and payments. Partici-
modate the same request rate. In other words,
pants of a distributed autonomous system behave
all nodes probabilistically receive uniform load if
selfishly, choosing strategies that would maximize
nodes are uniformly distributed across given ID
the payments they receive. Abstraction of strate-
space and if requested IDs are also uniformly
gies and payments is one of the key issues of
distributed.
a DAMD design.
higher load as a result of designated-node election
Since our interests are in autonomy, we are
1
356
Nodes may occasionally receive
algorithm, as in k-bucket node selection of
LETS (Local Exchange Trading System) is a form of community currency.
W
I
D
E
P
R
O
J
E
C
Kademlia[171], but they are only probabilistic
pretending as micro-node and still receive as
results. The underlying assumption of these DHT
much service as regular node.
algorithms is that uniform load — in terms of
ested to explore design space where fairness can
bandwidth, storage, and computation — is gen-
be ensured without losing simplicity and without
erally acceptable.
adding much overhead. Note that we are only
We are inter-
Such an assumption becomes unacceptable,
dealing with fairness in the sense that false adver-
however, if one starts to consider nodes with fewer
tisement of capability can be identified and greedy
resources, e.g., PDAs and home appliances with
use of foreign node’s resources can be alarmed; we
embedded micro-nodes. Nodes may have differ-
do not deal with the problem of skewed distribu-
ent kinds of resources; for example, their storage
tion of request rate among similar nodes.
may be either abundant or scarce, bandwidth may
This report describes extensions to Kademlia
be either narrow-band or broadband, and their
that introduce weight as a new node attribute,
connectivity may be either intermittent or per-
thus facilitating coexistence of lightweight nodes
sistent. Furthermore, nodes may have different
and heavyweight nodes, while at the same time
communication characteristics and they may also
maintaining fairness by probabilistic detection of
have different failure modes. In such heteroge-
misbehaving nodes.
neous environment, the underlying assumption of
heterogeneity and resource heterogeneity in this
uniform capacity should be abandoned in favor of
report; we do not consider heterogeneity in hard-
capacity-aware resource allocation.
ware/software architecture, assuming pervasive-
First, we are interested to address the following
We focus on performance
ness of today’s general purpose processor architecture and operating system architecture.
ent resources augment each other, in autonomous,
algorithm because of three reasons. First, it offers
mutually-serving overlay networks? More specifi-
tunable parameters, k and α, unlike other DHT
cally, can we exploit characteristics of some micro-
algorithms. While it has not been pointed out in
nodes in order to maintain overlay networks more
the original Kademlia paper, it is trivial to rede-
reliably? For example, refrigerator can be always-
fine k and α as node-local parameters. We con-
on node of particular overlay with energy-saving,
sider to change these parameters depending on the
slow processors and with few amount of mem-
weight of specific node.
ory, while PDA is intermittent node with modest
Second,
parallel
RPC
to
α
nodes
(in
amount of storage; we are interested to see DHT
FIND NODE and FIND VALUE RPCs) and
algorithms that can leverage such situations.
k nodes (in STORE RPC) can be exploited to
Second, we are interested to evaluate the fea-
combine desirable properties of nearby hetero-
sibility of extending existing DHT algorithms for
geneous nodes.
heterogeneity. The virtue of existing DHT algo-
persistent node can be used to reliably maintain
rithms is simplicity; if the extended DHT algo-
k-bucket, while fast and intermittent node can
rithm is very complex, it becomes very difficult
be used to quickly respond to FIND NODE
to communicate the idea and build further work
requests.
on it. In the meantime, complex algorithm would
require major modification to source code.
For example, relatively slow,
Third, knowledge of numerous neighbors can
be exploited in order to efficiently identify mis-
Third, we are interested to maintain fairness
behaving nodes without incurring much addi-
while at the same time accommodating hetero-
tional overhead. When the ID space consists of
geneity.
If we tolerate heterogeneity in DHT
d bits, Kademlia maintains contact information
algorithms, it becomes easy to misbehave, e.g., by
of kd nodes in the k-bucket, whereas Chord
357
24
Integrated Distributed Environment with Overlay Network
We have chosen Kademlia as our base DHT
●第 部
question: can heterogeneous nodes with differ-
24
Our motivation for this work is as follows.
T
w
●第 24 部 Integrated Distributed Environment with Overlay Network
maintains finger table of d nodes.
tree representation of ID space, it can be extended
trees, or as a single, uniformly heterogeneous tree.
degree of heterogeneity by introducing weight as
The former case can be implemented by using
a new node attribute, by making k and α node-
ID’s several most-significant bits as weight; the
local parameters, and by modifying α-node elec-
latter case can be implemented either by using
tion algorithm.
several least-significant bits as weight, or by defin-
t
show that Kademlia can accommodate arbitrary
Furthermore, we describe extensions to main-
r
either as a concatenation of multiple homogeneous
tain fairness in heterogeneous overlay so that
o
Our contribution in this report is as follows. We
nodes with different weight can be differentiated,
We introduce a new node attribute, weight,
while at the same time detecting unfair use of
since Kademlia does not offer explicit join or move
resources within the same weight. More specifi-
operation.
cally, we introduce two new RPCs, check fairness
a node becomes inaccessible if the node changes
ing a new attribute that is independently defined
If we spare either MSBs or LSBs,
a
u
n
discusses several ways to introduce heterogeneity
into DHT algorithms, and then describes our heterogeneity extension. Section 2.3 describes proba-
Weight is propagated through RPCs by includ-
bilistic mechanisms to assure correctness of weight
ing sender’s weight in every packet. Also, contact
and detect greedy use of foreign resources. The
is extended to <node ID, IP, UDP port, weight>,
feasibility and effectiveness of our method are
whereas it has been <node ID, IP, UDP port> in
evaluated in Section 2.4. Finally, Section 2.6 con-
the original.
cludes this report.
will give us similar effect to the weight attribute
as long as weight remains persistent.
The weight attribute can be used to modify
lows. In Kademlia, FIND RPCs to remote nodes
We simply deal with performance heterogeneity
return closest k nodes, and α nodes are selected
and resource heterogeneity by encoding them in
from closest k nodes with consideration to round-
single scalar value of weight. If single scalar value
trip time. We elaborate the selection algorithm
falls short of representing various combinations of
of α nodes by considering weight in addition to
performance heterogeneity and resource hetero-
round-trip time. During α iterations of node selec-
geneity, one can arbitrarily add similar scalar val-
tion, random variable w is chosen from skewed
ues to represent them. Our intent in this paper is
distribution and one node with weight w is picked
to concisely describe portions of base DHT algo-
up with consideration to round-trip time, so that
rithms that must be modified; expressiveness can
nodes with different weight receive FIND request
be better addressed at the implementation level.
at different request rate.
W
I
D
E
R
2.2 Heterogeneity in Kademlia
P
O
formity of ID space will be lost. The use of LSBs
FIND NODE and FIND VALUE RPCs as fol-
J
E
C
T
This report is organized as follows. Section 2.2
a
such possibility. Also, if we spare MSBs, the uni-
3
ment of weight, respectively.
0
nodes’ weight in this paper, it is desirable to leave
0
its weight. While we do not consider to change
2
RPC and check weight RPC, in order to detect
unfair escalation of k values and false advertise-
n
l
r
e
p
from ID.
For the convenience of discussion, let smaller
It should be noted that k and α are redefined
weight represent nodes with inferior performance
as node-local parameters that are derived from
and fewer resources, and let larger weight repre-
weight, whereas they have been static, globally
sent nodes with superior performance and richer
shared constant in the original Kademlia.
resources.
order to ensure fairness, the derivation table of
One can conceive several ways to accommodate
heterogeneity in ID space. Considering the binary
358
In
k and α from weight must be the same across all
participating nodes.
In addition, k must be
W
I
D
E
P
R
O
J
E
C
explicitly communicated to peers by including k
agrees with the original packet’s weight; if those
in FIND RPCs.
two values disagree, it signifies error to the sender.
Lightweight node can reduce both communi-
Note that maintaining weight of known nodes
cation and memory overhead by using smaller
is not a major overhead in any Kademlia imple-
weight.
Since k may become small, the node
mentation, since it keeps record of contacts for
can maintain and receive shorter list of contacts.
k-bucket, and it caches recently obtained contacts
More capable nodes can advertise larger weight,
for subsequent FIND RPCs.
so that they can maintain larger k-bucket for effi-
This
system
of
probabilistically
checking
cient lookup. Similarly, α can be controlled inde-
integrity of weight can be circumvented by mis-
pendently of k as long as α ≤ k.
behaving nodes, however. If a misbehaving node
The heterogeneity of k comes with some drawbacks, however.
T
disconnects for a while, wait for its ID to expire
If an RPC responder main-
from k-bucket and from cached contacts in foreign
tains a smaller k-bucket, it will return distant
nodes, and then it joins again, its weight can be
nodes even if the RPC initiator maintains larger
manipulated. This comes with penalty to the mis-
k-bucket. In order to minimize such situations,
behaving node, however: it cannot use resources
replies from nodes with larger k-bucket should
on the overlay for a while.
be preferred; replies from nodes with smaller
Another kind of manipulation attack would be
k-bucket should be used only in the event that
to change its node ID and join again to the same
other closest k nodes do not respond.
overlay with different weight. This cannot be prevented in most DHT algorithms, since they do not
preferential treatment of heavyweight nodes do
require signature of nodes that persists across ses-
not work; FIND RPCs will distribute load among
sions. In fact, such signature is very difficult to
lightweight nodes.
obtain unless one can define a way to associate
●第 部
If adjacent k nodes are of smallest weight, the
24
ity. A common alternative approach would be to
While weight can be used to accommodate
penalize newly joined nodes so that they cannot
nodes with orders of magnitude difference in
send requests for a while. We do not explore this
capacity, a mere scalar value could be easily forged
issue further in this paper.
to limit arrival rate, while at the same time max-
Once integrity of weight is ensured, it becomes
imizing request rate. We introduce simple mech-
possible to detect unacceptable degree of paral-
anisms to ensure fairness without adding much
lel queries that any given node is sending, since
overhead. We attempt to ensure fairness by iden-
k is directly derived from weight. We consider to
tifying false advertisement of weight, unaccept-
detect such an event without disclosing the tar-
able degree of parallel queries, and unacceptable
get that node in question is seeking for. This can
request rate.
be achieved by introducing check fairness RPC,
False advertisement of weight can be identified
which is also probabilistically generated by recipi-
as follows. Since weight of a given node should be
ent of FIND RPCs. Upon receipt of a FIND RPC,
the same across all foreign nodes, a node receiv-
each recipient generates check fairness RPC at
ing RPC sends a check weight RPC to a random
certain probability, then sends it to a node of dis-
node it knows of, with original packet’s sender and
tance k. Inside the check fairness RPC packet,
weight encoded. We can control the overhead of
(sender, target) tuple of the original FIND RPC
the check packet by generating packets on certain
is hashed to conceal the target. Upon receipt of
probability p. The recipient of check weight RPC
the check packet, the receiving node can detect
checks if known weight of the node in question
violation of k if the received hashed value matches
359
Integrated Distributed Environment with Overlay Network
2.3 Fairness in Kademlia
24
nodes with real-world entities of enough credibil-
w
●第 24 部 Integrated Distributed Environment with Overlay Network
parameters, in order to evaluate their effect on
get) tuple to the sender as a proof of possession.
both workload distribution and lookup efficiency.
The workload generation program runs as an over-
of distance k is included in the next iteration of
lay node which initiates requests and responds to
FIND query for the same target. In this case, the
other node’s requests. We used a test-bed environ-
sender of FIND RPCs will be incorrectly identi-
ment which consisted of 4 PCs interconnected by
fied as a misbehaving node. In order to minimize
a 100base-TX switch, each running 32 instances
such situations, the check fairness RPC should be
of the workload generation program. Each run of
sent immediately after receipt of FIND RPC. In
emulation consisted of 600 seconds; 12 runs with
addition, one can introduce delay before starting
different random seeds are conducted for each set
next iteration of FIND RPC, in order to assure
of parameters, in order to offset potential skew in
phased execution of both RPCs.
randomness.
a
u
request rate, with uniformly distributed weight,
n
ficult to detect unless α exceeds k. The realis-
and without any artificial delay or packet loss. In
n
tic solution would be to keep k small so that the
order to assure uniform distribution of weight, the
impact of manipulation could be minimized.
number of nodes for each weight has been kept
0
ing on the weight of sending node.
0
We also consider to rate-limit request dependbe implemented by keeping track of inter-arrival
2
3
The degree of parallelism can also be controlled
by manipulating α, but such manipulation is dif-
a
l
r
e
p
There can be such circumstances that a node
t
tuple for the sender. The node replies (sender, tar-
r
load generation program with different set of
o
the hashed value of the last known (sender, target)
This can
time of requests; such an extension is not a major
constant
constant. In the α-node selection algorithm, the
probability of choosing weight w, pw , is exponento its weight: p
tiallyp proportional
= 1.
w+1
= 2pw , and
w
Requests are generated as follows:
STORE
round-trip time to each node of k-bucket.
2.4 Evaluation
O
We have implemented basic part of Kademlia
R
requests randomly re-used recent targets. These
in C, and then extended it for heterogeneity and
P
J
requests are generated to random target in the ID
space, and both FIND VALUE and FIND NODE
E
C
T
overhead, since original Kademlia keeps track of
We used the following workload:
fairness. We have found that such extension can
We measured the number of FIND NODE pack-
be easily made. The original implementation con-
ets received, in 128-node emulations of w < 8 and
sisted of 2855 lines of code, whereas the enhanced
w < 4, with parameter k ranging from 5 to 20.
version consisted of 3512 lines of code. The addi-
The box-and-whisker plots of k = 5 are presented
tional code of 657 lines has been broken down in
in Fig. 2.1 and 2.2, while results for k = 20 are pre-
Table 2.1.
sented in Fig. 2.3 and 2.4. The α has been kept
three kinds of requests have been sent alternat-
W
I
D
E
ingly at every second.
Next, we ran the algorithm through single workTable 2.1. Breakdown of additional code
Category
k and weight
Modified node selection
check weight RPC
check fairness RPC
Request rate check
Hash function
Miscellaneous
Total
360
Lines
39
64
85
102
51
200
116
657
constant; α = 2 in all emulations. We confirmed
that highly skewed distribution of load among
classes can be attained by increasing maximum
weight from 4 to 8. The outliers of weight 0 are
particularly visible in Fig. 2.1 and 2.2, since an
initial node with weight 0 is designated as initial
rendezvous node; it accepts initial FIND NODE
requests from the rest of the nodes.
Interestingly,
the
number
of
received
FIND NODE packets are linearly proportional
W
Fig. 2.1. Distribution of received FIND NODE
D
E
P
R
O
J
E
C
T
Fig. 2.5. Distribution of received
FIND VALUE packets; k = 20, w < 8
packets; k = 5, w < 4
Fig. 2.2. Distribution of received FINDNODE
I
Fig. 2.6. Distribution of received
FIND VALUE packets; k = 5, w < 8
packets; k = 5, w < 8
exponentially proportional to weight. This can
●第 部
to weight, even though pw has been made
24
to all of the k closest nodes it has not yet queried,
making α-node selection algorithm affect more
weakly.
In
Fig. 2.3. Distribution of received FINDNODE
packets; k = 20, w < 4
contrast,
FIND VALUE
the
packets
number
of
exhibit
received
exponential
trend if k is large (Fig. 2.5); smaller k weakens
this trend (Fig. 2.6).
The exponential trend
is presented more strongly in FIND VALUE
because it can immediately terminate once the
RPC initiator obtains value from one of the
responders. In other words, the k-node lookup
for terminating the request, as employed in
FIND NODE, is not necessary as long as the
value exists.
Fig. 2.4. Distribution of received FINDNODE
packets; k = 20, w < 8
Next, we measured the effect of using different k values among classes. When we used k = 5
for w < 4 and k = 20 for w ≥ 4, the number of
FIND NODE packets became twice as much as
that of uniform k = 20 (Fig. 2.7).
This can
361
Integrated Distributed Environment with Overlay Network
Kademlia; it eventually resends the FIND NODE
24
be explained by the FIND NODE algorithm of
w
●第 24 部 Integrated Distributed Environment with Overlay Network
overlay in Brocade[329] are such examples. Such
approaches quickly become incomprehensible if
one attempts to construct multiple tiers of overlays.
These techniques may find it difficult to
accommodate nodes if they have orders of magnitude difference in bandwidth, processing power
and memory, and if their performance heterogenecategorized into two groups.
different k values
p
o
r
t
ity and resource heterogeneity cannot be simply
Fig. 2.7. Median of FIND NODE packets for
e
2.6 Conclusion
r
Many DHT algorithms assume that each par-
a
u
assumption becomes unacceptable if one attempts
n
to connect heterogeneous devices with single overlay.
Fig. 2.8. Empirical CDF of spoofed weight
packets observed at each node
to certain class of DHT algorithm. We described
0
extensions to Kademlia that introduce weight as
be intuitively explained as follows: nodes with
a new node attribute. Required modifications to
larger k-bucket require multiple replies from nodes
support weight are minimal: the α-node election
with smaller k-bucket in order to find the closest
algorithm and packet formats are enhanced to
take weight into account, and two key parameters
of Kademlia, k and α, are made node-local.
T
2
be accommodated by making minor modification
E
J
value should be limited to small fraction of nodes;
O
it can be useful when STORE requests to closest k
Furthermore, we have introduced two new
R
nodes are frequent, or when the memory require-
RPCs, check weight and check fairness RPCs, in
ment of larger k-bucket cannot be accommodated.
order to detect false advertisement of weight and
Next, we measured the detection rate of pack-
unfair escalation of k values. These RPCs are
ets with spoofed weight. In this test, one of the
probabilistically generated to detect misbehaving
128 nodes advertises false weight value for 180 sec-
nodes, thereby ensuring fairness.
W
I
D
E
k nodes. This implies that the use of smaller k
P
C
Such an
We have shown that resource heterogeneity can
0
3
a
amount of resource requirements.
n
l
ticipating node can accommodate comparable
onds and other nodes attempt to detect spoofed
The proposed enhancements are incorporated
weight by generating check weight packet at the
into our Kademlia code, through which we have
fixed rate of 0.78%. The empirical CDF of spoof
evaluated the feasibility of such extension.
observations at each node are plotted in Fig. 2.8.
a result, we have found that such extension can
Since spoofed packets are sent to random nodes
be easily made.
in the k-bucket, the results were almost identical
firmed that load distribution can be controlled by
regardless of k value.
weight and that false advertisement of weight can
be identified.
2.5 Related Work
Techniques exist to accommodate heterogeneity by creating two-tier structure on top of overlays: the expressway of eCAN[330] and secondary
362
As
Through emulations, we con-
W
I
D
E
P
R
O
J
E
C
T
3.1.2 Economy in autonomous distributed
systems
第 3 章 i-WAT: The Internet WAT System
— A Medium for Cooperation in Distributed
Recent interests in distributed algorithmic
mechanism design[80], unified efforts between eco-
Autonomous Systems —
nomics (mechanism design part) and computer
science (distributed algorithmic part), shows that
Abstract
researchers of distributed systems are beginning
i-WAT[250] to promote sustainable barter relationships among subsystems of a distributed
autonomous
system.
i-WAT
itself
is
to pay more attention to incentives for cooperation and fairness of sharing resources.
Distributed autonomous systems require coor-
an
dination among nodes to achieve their goals or
autonomous system, without necessitating a cen-
to satisfy their requirement specifications. Since
tral point of authority. It uses a digitally signed,
each node may behave selfishly to maximize its
electronic form of promissory note as the medium
benefit, sense of incentive-compatibility becomes
of exchange.
important, which is a state of the collection of
This report illustrates how it should assist build-
selfish behaviors of the nodes resulting in achieve-
ing of distributed autonomous systems and their
ment of the goal as the whole.
internetworking, and discusses, in particular, how
among nodes in such a system necessitate fair
trust can be maintained in such a currency system.
exchange of the computing resources. Media for
Among other means, the current design of
barter relationships seems an essential part of such
i-WAT allows the notes to be transported over Jab-
a design, which may take forms of points or barter
ber[186, 187] instant messaging protocol. A pro-
currencies[250].
Relationships
●第 部
totype of an i-WAT checkbook has been developed
24
3.2 Peer-to-peer currency
to experiment on the actual usage of the currency
3.2.1 Reason for peer-to-peer currency
system using the checkbook as well as provisional
web applications.
Money plays an important role in economy. As
a medium of exchange, it eliminates the need for
double coincidence of wants, in which each of the
3.1 Introduction
two parties is willing to consume what the other
3.1.1 Peer-to-peer is a form of economy
is producing. Resources are more effectively dis-
My Japanese dictionary says that economy is
tributed without such a need for coincidence.
“the act and process of production, distribution
Today, however, money looks more like a prob-
and consumption of goods and services which
lem than a solution. Its another role, a medium
forms the bases of human communities, and the
for accumulating wealth, has resulted in scarcity
whole body of social relationships built upon
of the media, dividing the world into haves and
such activities.” It is not just about saving but
have-nots, the former having control over the lat-
about how finite resources are distributed in or
ter.
among communities, which influences on how people interact with each other.
In
this
sense,
economy
To be independent from such control, and to
achieve sustainable local economy even in pres-
and
distributed
ence of attacks or global/national depressions,
autonomies, or so-called peer-to-peer, are closely
alternative forms of money have been proposed
related; in fact, peer-to-peer is a form of economy,
and tested. Successes of such experiments include
in which distribution of resources is performed
Wörgl[256] in 1932, in Comox Valley[258] in 1983
without the necessity for central coordination.
and in Ithaca[87] since 1991. The one in Comox
363
Integrated Distributed Environment with Overlay Network
as a plug-in for a Jabber client. We are beginning
24
This report proposes a currency system called
w
●第 24 部 Integrated Distributed Environment with Overlay Network
the creditor, and in return obtains the goods
Valley promoted barter relationships.
Many of the successes are short-lived, however,
because most designs of alternative money are
or service.
2. Using trade
To do so, he or she writes the name of the
their first administrations which were more ade-
payee on the back of the note. The payee
quately motivated than later ones.
becomes the new creditor, repeating which
t
tions. Many experiments owe their successes to
It would thus benefit the sustainability of econ-
the WAT note circulates among people. The
r
The creditor can use it for another trading.
omy if we could design a currency system without
length of the chain of creditors shows how
o
dependent on the qualities of their administra-
the necessity for central administration. As far as
p
much trust the note has gained.
3. Liquidating trade
r
e
sustainable economy is concerned, currencies, too,
The WAT note is invalidated when it returns,
need to be peer-to-peer.
WAT System is a free currency in the following
n
of promissory note called WAT note, a physical
a
existing peer-to-peer currency, in which a form
sheet of paper, is used as the medium of exchange.
3
WAT System[316] is one of a few examples of
Fig. 3.1 shows the three types of trade in WAT
0
u
3.2.2 Example of peer-to-peer currency
n
a
l
as a result of a trade, to the debtor.
System:
0
1. Administration-free
Anyone can spontaneously start WAT System
with a sheet of paper if they follow a few rules.
2. Interference-free
It is independent of national or global econ-
1. Drawing trade
omy.
A person in want of some goods or service
3. Free location
becomes a debtor, and issues a WAT note.
Any WAT note is compatible with any other
The debtor writes on the note the name of the
WAT notes in the world, and the currency
provider of the goods or service, the amount
system is globally operable (although within
E
C
T
2
ways:
The
R
debtor hands the note to the one who becomes
the limit where one’s credit can be trusted).
3.3 i -WAT: the Internet WAT
P
J
and the debtor’s signature.
of debt
O
2
3.3.1 Overview
E
We developed i-WAT[250] as an extension of
D
WAT System so that it can be used on the InterI
net. It is intended to be used by people or by
W
autonomous programs in distributed systems.
The medium of exchange in i-WAT is a message signed in OpenPGP[21], by which transferring the ownerships of electronically represented
WAT notes is implemented. The exchanged messages are called i-WAT messages, and the note
represented by the messages is called an i-WAT
note.
Table 3.1 shows the types of i-WAT message.
Fig. 3.1. Trading with a WAT note
2
364
All i-WAT messages are signed by its sender,
Typically in a unit called WAT, which represents cost of producing electricity from natural energy sources,
but anyone can create their own units.
W
I
D
E
P
R
O
J
E
C
T
Table 3.1. i-WAT messages
No.
Message name
Function
1
i-WAT <draw>
Draws an i-WAT note.
2
i-WAT <use>
Uses an i-WAT note.
3
i-WAT <accept>
Confirms the readiness to accept the provided i-WAT note
once its validity is verified.
4
i-WAT <reject>
Rejects an i-WAT note.
5
i-WAT <approve>
Guarantees the validity of an i-WAT note, and approves the
transaction.
6
i-WAT <disapprove>
Denies an i-WAT transaction.
and are formatted in the canonical form of
and sends an i-WAT <approve> message to
XML[17] which handles nested signatures well.
the creditor and payee, as well as all other
3.3.2 Protocol
at once, in order to assure atomicity of the
debtors in case multiple i-WAT notes are used
The three types of trade are implemented as
follows:
transaction; the notes will not be transferred
to the payee unless all <approve> messages
are collected.
3.3.2.1 Drawing trade
which contains the e-mail addresses of the
1. Like using trade, the creditor sends an i-WAT
<use> message to the payee.
2. If the payee equals the debtor, the debtor
sage becomes the original i-WAT note after
invalidates the i-WAT note as the debt is
the protocol is completed.
now liquidated.
2. The creditor sends back the i-WAT <draw>
message to the debtor. This is called i-WAT
<accept> message.
3. The debtor sends an i-WAT <approve> mes-
The debtor sends i-WAT
<approve> message to the creditor.
Fig. 3.2 shows the most complicated case where
a creditor uses multiple i-WAT notes issued by
different debtors.
sage to the creditor.
3.3.2.2 Using trade
1. The creditor adds to the i-WAT note the
e-mail address of the payee, and sends it to
the payee as i-WAT <use> message. This
becomes the valid i-WAT note after the protocol is completed.
2. The payee forwards the i-WAT <use> message to the debtor as an i-WAT <accept>
message. If the creditor wants to use multiple i-WAT notes at once, the payee must
forward all the i-WAT <use> messages to all
the debtors.
3. The debtor verifies the validity of the note,
Fig. 3.2. Trading with i-WAT messages
365
24
Integrated Distributed Environment with Overlay Network
number and the amount of debt. This mes-
●第 部
debtor and the creditor, an identification
3.3.2.3 Liquidating trade
24
1. The debtor sends i-WAT <draw> message
w
●第 24 部 Integrated Distributed Environment with Overlay Network
tion roots for a given item, based on the DHT
3.4.1 DCR: Distributed Consumer Reports
algorithm in use. For a different item, a differ-
DCR is an attempt to create a structure
ent set of nodes would be selected as its roots.
for administration-free exchange of information
The selection is made autonomously and deter-
among consumers about the goods and services
ministically (perhaps as part of location protocol)
they use. Its challenges are to maintain liveness
without imposing an expensive agreement pro-
t
of and credibility to the circulated information,
tocol. Reports are compiled at the information
to which we approach by letting subscribers of
roots based on the information gathered from the
reports make payments in i-WAT to the reporters,
reporters (nodes B and C). A subscriber (node D)
thereby offering the information providers motiva-
can obtain the reports from either of the informa-
tion and responsibility.
tion roots (decided by proximity), and pays an
r
e
p
o
3.4 Applications
r
In the figure, nodes A and E are the informa-
l
The current design of DCR utilizes DHT (Disa
u
n
n
predefined salts (such as 0, 1 and 2) to the item’s
or disseminated among registered users.
key4 , in order to avoid having a single point of
example of data dissemination over a DHT-based
failure.
overlay network is found in [331].
0
ple nodes responsible for a given item, by suffixing
Fig. 3.3 shows how DHT and i-WAT can be
0
to be used is still undecided. DCR makes multi-
applied to making and circulating distributed con-
2
tributed Hash Table) , but the specific algorithm
a
agreed amount in i-WAT to the one they choose
3
3
sumer reports.
to use. The paid amount is shared among the root
and the reporters.
The reports can be either obtained by queries,
An
3.4.2 Share-ik: an alternative copyright sys-
tem
T
Our research group is developing an alter-
E
J
materials.
R
ages derivation of new work from copyleft[86]
Share-ik is essentially a set of rules close to the
P
(Share intelligence and knowledge), which encour-
O
C
native copyright system named Share-ik [156]
GNU General Public License[85], which defines
E
a logical shared space from which public domain
D
materials and their descenders may not leave. In
I
order to apply this idea of “copyleft” to artistic
W
creations such as music, Share-ik adds a rule for
mutual evaluation: when new work is produced
by reusing some existing work in the shared space,
Fig. 3.3. Application of DHT and i-WAT to
consumer reports
3
4
366
the reuser is asked to make a payment in i-WAT
(in a unit called share) to the authors of the
In short, DHT provides a lookup service of <key, value> pairs. It provides an application-independent
function which maps a key to the responsible node in the system. Typically, keys and node identifiers
share the same n-bit name space, and are evenly distributed in the space using a one-way hash function.
Given a key (and a message), a DHT system will find a corresponding node (location), and optionally
routes the message to it (routing), which may return an application-specific value. Both location and
routing are deterministic, and performed within a bounded number of overlay hops, which typically grows
logarithmically to the number of participating nodes. This is more desirable for many applications than
broadcasting search requests as seen in Gnutella[225]. Several DHT-based overlay network prototypes have
been proposed, including Chord[271], CAN[237], Tapestry[328] and Pastry[248].
A technique introduced by Tapestry[328].
W
I
D
E
P
R
O
J
E
C
T
original work whom they appreciate. i-WAT protocol lets the original authors choose not to receive
the payment for typically two reasons: 1) they
do not agree with the new creation, or 2) a distributed auditing (section 3.6.3) shows that the
credibility of the reuser is doubtful. The latter
can be a result of their work not being appreciated by others in the community, leading to much
less income in share than its outlay.
In this way, the original authors can know how
much appreciation their works are receiving, and
the reuser can know whether their creation was
agreeable to the original authors, or if they are
Fig. 3.4. Defusing spam in spam-free e-mail
exchange
welcome in the community.
The result of the mutual evaluation is made
publicly available within opus information documents formatted in the canonical form of XML,
which allows partial content to be signed, so that
the signatures of the authors of original work can
be verified by other users.
●第 部
3.4.3 SAFEE: SpAm-Free E-mail Exchange
SAFEE takes a psycho-economical approach to
24
feels a loss rather than a benefit. Our solution
is to counterbalance the loss with an i-WAT pay-
Fig. 3.5. Prevention of spam in spam-free
ment. The unit of payment in SAFEE is called
e-mail exchange
MU (Mail Unit).
In SAFEE, there is one simple rule:
The sender of a message must pay 1MU to
each receiver of the message.
The assumption here is that if any two par-
payment. Fig. 3.4 illustrates this idea of defusing
spam.
This message transfer system can be augmented
by a rule for the message transfer agents:
ties have a healthy relationship, on average the
A transfer agent must reject relaying a mes-
amount of messages exchanged between them is
sage if the negative balance of the sender’s
evenly balanced, and they should not feel loss (a
MU account is more than max MU.
difference within several messages is not a prob-
where max is sufficiently large so that it does not
lem as i-WAT has a weak budgetary constraint).
prevent ordinary people from sending messages.
On the other hand, few people would reply to
A distributed auditing (section 3.6.3) can be used
unsolicited e-mail, which means that the sender
for checking the sender’s account. Fig. 3.5 illus-
loses 1MU for each receiver of their message. The
trates this idea of preventing spam.
receivers gain 1MU each, which they can use for
Obvious problem with SAFEE is that since
sending an e-mail message or exchange with other
i-WAT is based on OpenPGP, it is easy to forge
i-WAT currencies; the loss is compensated by the
one’s identity by creating key pairs for arbitrary
367
Integrated Distributed Environment with Overlay Network
as an e-mail message receiving which the receiver
24
solve the problem of spam. Let us define spam
w
●第 24 部 Integrated Distributed Environment with Overlay Network
e-mail accounts. To handle such situations, the
not promote a fair exchange. Therefore, instead
transfer agents can also check with a DCR query
of using accumulation of notes, we use accumula-
if the public key of the sender is backed up by
tion of trust of the nodes to build an incentive-
trusted signatures. Also, the trust values of the
compatible mechanism. Our hypothesis is that
senders obtained from a distributed auditing (sec-
trust can be expressed by how much transactions
tion 3.6.3) may be used for prioritizing the trans-
the node has successfully processed.
fer requests.
For example, the trust value of a node can be
3.4.4 Other possibilities
as an incentive for the node to make transactions,
Other, still highly conceptual applications of
and prompts the node for both using notes in pos-
i-WAT include what we tentatively call ATP
session and providing services for liquidating its
(Associating Transportations and Pedestrians). It
debt, so that its income and outlay are balanced.
r
e
p
o
r
t
expressed in the following formula, which works
a
u
a
ation of which is discussed in section 3.7.2.
Some apparent questions in designing an
3
n
This is the basic formula we use for now, a vari-
OSMOSE-like vehicle and its surrounding systems
0
a pedestrian or two who would like a ride.
income × outlay
|income − outlay| + 1
are trust and economy: what if the guest turns
0
know its destination, and the driver can pick up
trust = log
out to be a mugger, or driver a kidnapper? Is it
with values. Such values include i-WAT notes in
2
cle introduced by CITROËN at Paris Motor Show
2000. An OSMOSE vehicle can let pedestrians
n
l
is inspired by OSMOSE[169], a conceptual vehi-
morally or economically adequate to allow, quite
different units in different currencies.
The semantics of i-WAT inherited from WAT
System allows the notes to be freely associated
Fig. 3.6 shows how i-WAT notes in different cur-
E
J
should work regardless of locations (because vehicles travel).
requirements.
P
authentication and showing appreciation, which
O
provide solutions, there need to be mechanisms of
R
C
T
literally, free ride? To answer these questions and
3.5.2 Example of exchange mechanism
i-WAT seems to satisfy all these
rencies can be exchanged with one another.
The figure shows three communities, A, B
and C, depicted as rings.
These communities
can be circles of people, rings of Chord[271] or
some other forms of distributed hash tables, or
Also being investigated is a free currency lim-
I
3.5 Internetworking with i -WAT
W
D
E
ited for educational purposes.
3.5.1 Incentives for internetworking
There needs to be reasons for nodes to participate in and cooperate across multiple peerto-peer systems or even within a single peerto-peer system. Although i-WAT may work as
a medium of exchange, that alone does not mean
that it will assist the designs of actual distributed
autonomous systems. We need to provide a mechanism for incentives and fairness.
In a monetary economy, accumulation of bank
notes forms an incentive. As we described earlier, this results in scarcity of the media, and does
368
Fig. 3.6. Exchanging i-WAT notes among different currencies
W
I
D
E
P
R
O
J
E
C
just any groups of nodes in autonomous overlay
i-WAT note to travel across communities, the note
networks. We assume that methods for message-
would be more trusted if it stayed within one
routing exist among these communities. The com-
community. This is the reason for the need for
munities use currencies A , B and C respectively.
exchange points described in section 3.5.2.
T
An entity belonging to both communities A
and B can become an exchange point between
currencies A and B . Such an exchange point can
3.6.2 ID’s accountability
The most frequent criticism against i-WAT is
take a note in A , and draw a new note in B . The
that it uses e-mail addresses (or whatever IDs cou-
value of the new note is backed up by the exchange
pled with PGP public keys) for identifying parties,
point’s possession of the original note in A ,
A node in community A can ask the exchange
point to draw a note in B in return of a note
which can be changed, reused or forged easily.
Suppose a PGP key-pair is generated for an
imaginary person. Since the immediate parties
in A , The obtained note can be used to ask for
of transactions must contain each other’s trusted
some service in community B. i-WAT requires
public key in i-WAT, the public key of the imag-
that the each end of a transaction must have the
inary person must be signed by someone directly
other’s trusted public key. Those public keys can
in acquaintance with the person: the creator of
be signed by the exchange point.
the person and thus, the forger. In order for the
public key to be transitively trusted, the forger
the drawn notes and give up the original notes,
must be included in the chain of the creditors. If
as it will insure the increase of their trust val-
the imaginary person fails to liquidate the debt, as
ues. They are also motivated to advertise their
the forger intends, the forger him or herself must
services.
take over the debt being its immediate creditor.
If someone in community B wants to issue a note
Therefore the cost of lying is considered high.
●第 部
The exchange points are motivated to collect
24
and A to C .
3.6.3 Distributed auditing
Since i-WAT is decentralized, calculation of
the trust values of participating nodes needs to
3.6 Discussions on trust
be achieved by collecting information from each
3.6.1 Embedded locality
transaction, and constructing an image of the
In i-WAT, the debtors need to have the trusted
node’s account based on that information. There
public keys of all creditors appearing in the life-
is no guarantee that the collected information
cycle of the notes they issued, because they are
is truthful if there are incentives for lying or
responsible for verifying all the transactions using
colluding.
the notes.
In order to tackle this problem, we first take
Some argues that it is unlikely to happen in
a look at how a user’s account information can be
real-life. Bu we believe that this defines the sys-
used for calculating their trust values. Table 3.2
tem’s locality; the above condition can easily be
shows how records of notes in a user’s checkbook
satisfied in a small group of people closely work-
can be used in measuring their trusts.
ing together, where every one can verify and sign
We argue that the following statements are true:
each other’s public key. The condition can also be
1. There is no incentive to conceal the records
satisfied, albeit marginally, according to the tran-
of liquidated or used notes.
sitive nature of trust in PGP[1], because the both
The users would not claim less income and
parties of a transaction must have each other’s
outlay in balance than there actually is be-
trusted public keys. While it is possible for an
cause that would decrease their trust values.
369
Integrated Distributed Environment with Overlay Network
points in Fig. 3.6 to exchange a note in B to A
24
in currency C , then they use the two exchange
w
●第 24 部 Integrated Distributed Environment with Overlay Network
Table 3.2. Meanings of i-WAT notes in the checkbook
Note that in the above protocols, CD-1 and
ing to have drawn more notes, or more credit
CC-2, as well as CD-2 and CC-1, are indistin-
by claiming to possess more notes drawn by
guishable to the receiving end of the queries.
someone else, because they may be asked for
Therefore there are disincentives to lie to the
a proof in an auditing process.
queries.
If there is a proof, we believe that it should be
A debtor and the immediate creditor may have
considered a set of different problems: trans-
a reason to collude. They might lie that the transaction never took place. However, the relationship between a debtor and the immediate credi-
We believe
tor is not symmetrical. It is riskier for the creditor
because lying means denial of their crediting debt.
We are investigating further to make the dis-
a
u
and inflation of the value system which might
n
result from such transactions.
n
there can be operational solutions for this
a
sort of problems, and experimenting on solu-
3
tions in the actual barter economies described
later.
3. The only reasonable way to tell a lie is not to
reveal the existence of debits or credits.
tribute auditing an inexpensive process.
3.6.4 Sustainability
Trust is also dependent on sustainability of
As a countermeasure for this, we can apply
i-WAT itself.
i-WAT inherits the polycentric
the protocol for fair sharing described in [211].
nature of WAT System, and should be difficult
E
J
O
P
CD-2. For each note in the list, the one asks
E
session of notes.
its debtor for the list of drawn notes.
D
chosen user, one asks for a list of their pos-
CD-3. If the note in question is not included
I
CD-1. At a random interval, to a randomly
in the list, the debtor is lying about their
W
Protocol to detect concealed debits (CD):
R
C
T
2
0
actions without actual practice of bartering,
0
l
r
e
p
2. One cannot lie to have more debits by claimt
Role in trust value
Balanced income and outlay
Negative balance or debit
Positive balance or credit
Balanced income and outlay
r
Description
Liquidated
Not liquidated
Possessed
Used
o
Debtor of the note
This user
This user
Not this user
Not this user
debit.
to break.
In i-WAT, the debtor is responsible for guaranteeing that the circulated note is not a fraud. In
this sense the debtor is privileged, but it is not
a single point of failure because once the debtor
fails the immediate creditor takes the debtor’s
role; the function of the debtor follows the chain
of creditors.
Which means that the rational behavior is never
to take an i-WAT note directly from a debtor.
Protocol to detect concealed credits (CC):
Wwhile it is very true, people do not always act
CC-1. At a random interval, to a randomly
rationally, especially in a small group of people
chosen debtor, one asks for a list of their
where everyone knows each other well. There is
drawn notes.
some risk if a note travels across communities, but
CC-2. For each note in the list, the one asks
as described in section 3.5.2, a community mem-
its current owner for the list of all notes
ber is never obliged to take notes issued by mem-
they possess.
bers of other communities.
CC-3. If the note in question is not included
in the list, the creditor is lying about their
credit.
370
W
I
D
E
P
R
O
J
E
C
T
value is called WIDE Power, given by the follow3.7 Deployment and experiments
3.7.1 Jabber-based i -WAT
i-WAT needs a decentralized message transport
to assure its sustainability. While a DHT-based
overlay network is being investigated to provide
such functionality, we need to verify the design of
i-WAT by quickly deploying it even in absence of
a desired infrastructure.
ing formula:
WIDE Power
income × outlay
− penalty
= log
|income − outlay| + 1
where penalty is decided by the administration.
The maximum WIDE Hours each member can
spend are limited to 24 WIDE Hours a day.
WIDE Hour was introduced in a four-day meet-
i-WAT allows the underlying carrier of mes-
ing in September 2003, and more than 600 trans-
sages to be existing e-mail or presence/instant
actions had been processed by the end of year
messaging system.
A prototype of an i-WAT
2003.
checkbook has been developed as a plug-in for
available to public soon.
3.7.3 Internetworking
between
web
and
peer-to-peer barter currencies
A pre-release version has been used by a small
i-WAT can also implement WIDE Hour, and we
group, and there are some findings. In particu-
are planning to connect the two implementations
lar, we discovered that even people with sufficient
together in March 2004. Fig. 3.7 illustrates how
knowledge of PGP found the key exchange cum-
it should work.
WIDE Project has a strict notion of member-
for secure public key exchange as a subsystem of
ship, but its activities often involve non-members.
i-WAT.
While it does not always make sense to provide
non-members with accounts in OMELETS version
3.7.2 OMELETS and WIDE Hour
networking mechanism, such notes can be made
system as if the account information comes from
compatible with the OMELETS version of WIDE
central sources.
Hour.
There is an example of a barter currency with
central authority called LETS (Local Exchange
Trading System), which was first introduced in
Comox Valley[258] in 1983.
We have developed OMELETS (Open, Modular and Extensible LETS), a collection of Java
classes to implement LETS as a web application,
in the hope that it becomes useful in verifying the
designs of mechanisms using barter currencies.
An application of OMELETS have been developed for WIDE Project[318], a research project
of distributed systems which has more than 700
The barter currency for the
project is called WIDE Hour[317] (the web site
ber of hours of labor for the project. The trust
Fig. 3.7. Exchanging WIDE Hours outside the
WIDE members
371
Integrated Distributed Environment with Overlay Network
always be issued outside the project. By the inter-
tion 3.6.3, we can treat the peer-to-peer currency
is for WIDE members only), based on the num-
24
of WIDE Hour, i-WAT notes in WIDE Hour can
With the distributed auditing described in sec-
active members.
●第 部
bersome. Perhaps there needs to be a support
24
a Jabber[186, 187] client, which will be made
w
●第 24 部 Integrated Distributed Environment with Overlay Network
In the figure, there are two types of overlays.
One is the overlays of activity groups, and the
provisional web applications has been developed.
Experiments are ongoing.
other is the overlay of OMELETS version of
WIDE Hour. The former is peer-to-peer and the
latter is a star network.
The former overlays
can interact with each other using i-WAT notes
such a note by asking WIDE Hour Office for an
exchange.
Abstract
It works just like the exchange point in Fig. 3.6,
Advancement in wireless networking and mobile
only that the office accepts payments in LETS,
computing technology has brought a new chance
which backs up the value of the new i-WAT
to communicate not only with a particular per-
note.
son but with general public who are in a specific
l
r
e
p
o
t
A WIDE member can obtain
r
in WIDE Hour.
第 4 章 Design of Content Cruising System
n
n
of communication. If these contents are bound to
ID[8]-compliant 2.45 GHz RFID (Radio Fre-
appropriate time and place, the value of contents
quency IDentification) tag.
becomes higher for both senders and receivers.
The barter economy of MANA allows the users
The goal of our research is to realize a new
to obtain points by visiting certain locations
content distribution model where contents will
where RFID readers are placed, and having their
be gathered only into specific area autonomously
books identified by the readers. Obtained points
without centralized management but with coop-
can be used in a community residing on the
eration of mobile nodes. The use of this model
web[179].
will give users a freedom to send or leave contents
J
This is a large-scale experiment; about 10,000
about specific location and time, as well as giv-
O
copies of the book is expected to be circulated
ing users a chance to receive all the information
R
by March 2004, and we expect that about 2,000
bound to their locations.
P
E
C
T
0
involving a book[203] equipped with an Auto-
0
and traffic information are suitable for this kind
2
MANA is another application of OMELETS,
a
tents such as advertisement to a specific region
3
u
a
area in real space. Geographically dependent con3.7.4 MANA
people will participate in the experiment.
The achievements of our previous research were
published as a set of proceeding papers[136, 137].
between web and peer-to-peer currencies using
In this report, we present the design of a sim-
this barter economy, too.
ple but robust model to exchange contents among
I
D
E
We plan to experiment on internetworking
W
nodes within certain locations. We call the model
3.8 Conclusions
“Content Cruising System (CSS)”. CCS is a kind
This report proposed usage of a peer-to-peer
of peer-to-peer system which requires nodes to
currency system called i-WAT to promote sus-
collaborate with one another using a commonly
tainable barter relationships among subsystems of
shared transmission algorithm.
a distributed autonomous system.
i-WAT inherited its polycentric nature from
4.1 Introduction
WAT System, its predecessor in the physical
There are many kinds of information surround-
world. It is carefully designed not to introduce
ing our lives which depend on geography. The
any single point of failure. Trust is also main-
information such as advertisements of local stores
tained without necessitating a central authority.
or traffic information is more appreciated when it
A prototype of an i-WAT checkbook as well as
372
is distributed to people living or visiting nearby
W
I
D
E
P
R
O
J
E
C
rather than to people in distant locations. Such
layer, using “physical movements” of the mobile
contents will have higher value when they are
nodes. This approach is not always premised on
shared among people in that specific time and
routing on the network which has fixed durabil-
place.
ity. A content is broadly stored through a chain of
exist
distribution
geographically-dependent
services
contents
to
of
accidental and temporary communication events
mobile
performed when mobile nodes move close to one
nodes according to their locations. Such services
another (we define this as “Ad-hoc Communi-
are generally called “location-based services.”
cation”). The content has a chance to be for-
These services are divided roughly into two patterns of approaches.
warded further during some physical movement
of a node, resulting in a distant unspecified node
One is to provide contents to wide areas, by
receiving contents. This is a mechanism similar to
utilizing cellular phones, for instance [139]. This
rumor, word-of-mouth communication in actual
approach requires costly equipments and presence
societies, so transmitted contents are spread dis-
of a central management, which limits the users’
orderly through multi-hop communication. How-
freedom of communication. Moreover, it makes
ever, such information flooding can be suppressed
the services not dependable, in a disastrous situa-
to fixed geographical areas by using each node’s
tion where the infrastructure is damaged, or when
location information (which obtained from com-
we are in some developing region without such an
monly used device such as a GPS receiver), and we
infrastructure in the first place.
hope that this mechanism will establish some new
The other is to provide contents to local areas,
communication models depending on the loca-
with a number of hotspots and divide each area
tions of people.
in pieces [34]. The use of this kind of services
tents to remain in a specific area, the mobile nodes
is limited to places with hotspots. Moreover, it
which exist in the specific place will transmit these
is difficult for content senders to appoint target
contents to one another. Furthermore, since this
areas minutely.
communication model is independent from each
If it is possible to make con-
conducting researches on building another struc-
enters into the area will receive the remaining con-
ture to propagate contents depending on the loca-
tent, so the content-exchanging among the nodes
tions of nodes.
will be kept in the specific area now and in the
In this report, we propose a simple but robust
future.
This can also be a robust information
model to distribute contents used in real space,
system for guiding people to some destinations,
wireless communication environment. We call it
or seeking a missing person in a disastrous situa-
“Content Cruising System” (CCS).
tion where usual means for communication are no
The main
aspect of proposed model is that it does not
longer reliable.
require centralized servers to distribute informa-
The content transfer model performed on the
tion, and it does not depend on types of network
Internet so far is the movement of the content
connections either. In this model, nodes them-
between the nodes fixed on the network. Opposed
selves exchange contents with one another, with-
to this model, the content transfer model we are
out requiring the presence of content servers or
proposing is so to speak a “locally circularizing
network infrastructures.
model”, because the node itself moves and gathers the content which is fixed locally, and leaves
4.2 Approach
the content to an area to attain the content trans-
We have been studying a structure of another
fer among unspecified nodes. Although we do not
content propagation method in the application
specify the format of contents in our system, we
373
Integrated Distributed Environment with Overlay Network
node’s network-reachability, the node that newly
●第 部
In order to solve such limitations, we have been
24
24
There
T
w
●第 24 部 Integrated Distributed Environment with Overlay Network
assume the contents to be small in size, such as
simple method for delivering contents to unspeci-
voice messages or pictured maps, in the real-world
fied number of users being close in the real world.
applications.
In order to achieve this goal, it utilizes excess computing resources in each node, as well as excess
4.3 Related Work
network resources. Contents are autonomously
the contents and communication method below
the application layer.
This method is realized by adding geographic
information to the internet protocol. Ad-hoc network can be formed using one of many routing
CCS is operated by cooperation of servant
protocols which are different from the internet
applications which have same function installed
protocol. In MANET [194], the way of location
on mobile nodes, and the thrown-in contents cir-
based routing, or multicasting a packet to two or
culate through “store and forward catenation”
with neither continuous formation nor negotiation
among the nodes.
a
u
n
a
In a sense, our aim is to develop a kind of dis-
3
layer protocols in the future.
tributed content storage system in real space. In
0
These may be suitable for our system as lower
the field of overlay network, there are many pro-
0
area on the Ad-hoc network is examined[157, 166].
posed ways for designing distributed storage sys-
2
more nodes which exist in a specified geographic
n
l
r
e
p
t
areas. Therefore, CCS will not limit the size of
r
converged into targeted areas and kept in those
o
“Geocast”[205] is well-known as a method of
location-based communication on the Internet.
tem[39, 163, 271, 328]. As a commonly-observed
eral scheme listed below.
• Location based transmission: contents are
transferred and sustained in a specified area
autonomously.
• Location-aware: contents are found by people
in a relevant location
• Context based selection: unnecessary con-
table as a file name space, and provide distributed
tents are eliminated based on the user’s context.
T
feature, these mechanisms use distributed hash
E
data storage and ways for searching data effec-
J
tively. These approaches are efficient in terms of
O
decentralization of contents, although our mech-
R
anism requires that the contents are weighed by
P
C
The Objective of this system is to build a gen-
their physical locations. Above all, “Freenet”[39]
We are assuming there are some specific con-
has interesting mechanisms for content distribu-
ditions in ad-hoc communication, compared to
tion: anonymity and encryption of the contents.
usual communication environments. Therefore we
We have similar requirements on relaying contents
will model the communication environment and
in real space.
settle the conditions to perform the content trans-
4.4.2 Analysis of Communication Environ-
W
I
D
E
ment
ferring described in the foregoing paragraph.
4.4 System Design
4.4.1 Overview
Based on the concept described earlier, we
designed a mobile peer-to-peer location based con-
Hardware Requirements
Our target machines have functional capability
shown in Table 4.1.
tent distribution model called “Content Cruising System” (CCS), and devised a transmission
algorithm based on location information when
exchanging contents among mobile nodes in a real
space wireless ad-hoc communication.
CCS sets its goal on providing highly robust and
374
Functional Requirements
Besides a computing power, each node has at
least the following four functions:
• Receive the content
• Transmit the content
W
I
D
E
P
R
O
J
E
C
T
Table 4.1. Hardware Requirements
Functional capability
communicate with neighbor nodes
store data
sense self status
Assumed hardware
IrDA, Bluetooth, Wireless-LAN,etc.
HDD, RAM, Silicondisc, etc.
GPS, Clock, and other sensors.
• Display (or play) the content
a whole will become possible. As an item in the
• Store the contents
common requirements, we decide to use the each
node’s context (including its location and time),
With the kind of ad-hoc communication mentioned above in mind, we set the following prerequisites of communication:
which is acquired by their own sensors as a trigger for each node’s action (sending, displaying, or
accumulating).
On that basis, the sender adds meta data to the
• No specific management serves.
content header called COMPASS (COmmon Mes-
• Each node is independent and not controlled
sage PASsing Sheet), which includes the expected
mutually.
destination point and time in order to share ways
• Autokinetic communication by cell broadcast.
of handling the contents in all participating nodes.
• The content sender does not have knowledge
Receiving nodes compare their own context with
of the receiver’s situations or location.
• Limit on each node’s disk space.
their actions.
Selection of Contents
Since each node has limited storage capacity,
nication, we assume there are no negotiations
a mechanism is needed for automatically deselect-
among the mobile nodes for transmitting contents
ing contents that do not match the user’s context.
which are once thrown-in. Therefore, it is needed
We consulted the LRU algorithm[278] that data
to satisfy some functional requirements in order
will be eliminated from the domain where operat-
to realize the structure of CCS.
ing frequency is low when cache is full. Moreover,
The required functions and our solution are
each content has its own predefined duration.
described below.
Weighting Content and Transmission algoUnique Content ID
rithm
To avoid duplication of the contents, unique
To avoid meaningless flooding of contents, the
identifiers will be needed for each content. In cre-
sender must define “the condition in which the
ating a unique identifier, we plan to use a kind
content becomes most valuable” and transfer it
of one way hash functions such as SHA1[204] or
to the other nodes.
MD5[246] based on the combination of the MAC
service, the contents become most valuable when
address and content generation time.
they reach their destination points. Therefore, the
Using as a location-based
value of each content is defined as a unit in “CenContext Awareness
tripetal Force” from the destination point.
Because each node is independent, it is impossible to take any action without some kind of
trigger. By configuring the trigger as a common
requirement among servants, collaboration as
4.4.4 Configuration of Transmission algo-
rithm
If each of the contents has a specific target
375
24
Integrated Distributed Environment with Overlay Network
According to the conditions of ad-hoc commu-
●第 部
4.4.3 Requirements
the COMPASS, and use it as a trigger to decide
24
Prerequisites of Communication
w
●第 24 部 Integrated Distributed Environment with Overlay Network
F (d) = ae−kd
region, the Centripetal Force should be maximized only in that area which has a specific
shape (orthogon, circle, oval, etc.). However this
method is not suitable for our system because each
content’s Centripetal Force is apt to be conflicted
in overlapping portions where many con-tents are
t
deal with numerous contents as well.
In order to avoid the confliction, Centripetal
p
o
as long as there are mo-bile nodes. It also has to
r
thrown-in. Our system aims to cover any places
r
e
Force should be calculated relatively between each
node’s present location point and the content’s
a
u
n
n
ical movements of participating nodes, in contrast
to the other aim to sustain contents in certain
range. Therefore we thought the Centripetal Force
should not be regulated in obvious range by the
system.
2
3
for each content to be transmitted widely by phys-
0
In addition, our system aims to leave the chance
0
because “point” is more innumerable than “area”.
a
l
destination point rather than between those areas,
Based on above reasons, we chose exponentripetal Force among the other monotone decrease
function to start with.
The Centripetal Force is calculated as follows:
“a” is the value at the destination, ”k” is the
parameter which define the dependence with distance.
Every content is affected by this Centripetal
Force, and every node which possesses the content
does the same actions according to Centripetal
Force felt in the location.
As previously mentioned, Centripetal Force is
a reference to measure the importance of the contents in that location. The receiving ratio at each
point should be similar to the Centripetal Force
respectively. Hence, CCS uses the reciprocal of
the exponential function above as the time interval for the next transmission to take place.
The relation between the Centripetal Force and
interval times of sending is shown in Fig. 4.1.
4.4.5 Framework of Servant Application
In the CCS environment, all nodes have the
same unsophisticated functions performing common behaviors. The functions of the servant are
comprised from the following four modules. Their
relation is shown in Fig. 4.2.
W
I
D
E
P
R
O
J
E
C
T
tial decrease as a formula to calculate the Cen-
“d” is the distance from the destination point,
Fig. 4.1. The relation between the Centripetal Force and interval times of sending
376
W
I
D
E
P
R
O
J
E
C
T
circularized in the specific area.
4.5 Future Prospects
Though only the information distribution model
to many and unspecified people is dealt with in
this report, it is also possible to carry out a specific partner and specific content switching by the
secrecy of a content and a user’s authentication
using Hashed-Key technology[204, 246].
This mechanism would be needed to avoid
Fig. 4.2. Relation of servant modules
Denial-of-Service such as inserting a large number of junk files[39].
Sender Module
Moreover, in the present circumstances, medi-
This module sends contents which are stored in
ator is premised to transmit every content it
the Storage module to the neighbor nodes accord-
received, but the contents should be weeded out
ing to the direction by the Context Manager.
according to a certain demand of users for them,
Contents are broadcasted to all nodes in its radio
as it is the case for rumors.
signal range.
In addition, we substituted transmitting frequency for Centripetal Force this time, but in
This module receives content from the other
efficient resource management for the problem of
a transmission bandwidth and that of node’s electric power.
Storage Module
24
CCS makes various distribution models possible by giving transmission rules to a COM-
order, because the more adequate the content is,
PASS. Besides the distribution model treated as
the more frequently it is received, according to
an example in this report, the various distribu-
the transmission algorithm of CCS. The content
tion models with the combination of different rules
which is staying longer than its predefined dura-
(such as a content-distribution using a mediation
tion is deleted by Context manager’s command.
person’s or their transportation devices’ charac-
Before storing each content, the storage mod-
teristic, content-distribution using the reservation
ule compares the Content ID of the new content
function by time, and so on) should be considered.
with those of the old ones which the node has ever
module discards the old content.
4.6 Summary
The purpose of our research is to realize the
contents distribution system which is decentral-
Context/Status Manager
This module get information of the condition
of the node (defined as“Context”)from its sen-
ized in form that mobile nodes distributed in various places sharing the functions to store and to
distribute the contents.
sor (GPS, clock, etc.) continually. It compares
In this report, we proposed the design of
the context of the node with the COMPASS
Content Cruising System to realize the form
of the content, and calculates the Centripetal
of a decentralized content-transmission system
Force to prompt each module to function ade-
in real space.
quately in order for the content to be distributed/
mechanism in which contents are transmitted
This system brings about the
377
Integrated Distributed Environment with Overlay Network
This module stores the received content in FIFO
received. If duplication is detected, the storage
●第 部
nodes, and put it into Storage module.
case it is required engineering design about an
24
Receiver Module
w
●第 24 部 Integrated Distributed Environment with Overlay Network
autonomously, by adopting a simple algorithm
report, the term equivalent is loosely as ‘to share
in ad-hoc communication.
The catenation of
one or more common characteristics’ and a peer
content-transmission in a specific area provides
group is a group of nodes that share such charac-
for location based communication that does not
teristics. For example, group of printer and group
require a specific server or a specific infrastruc-
of nodes in a room are both peer group.
ture.
Project
original simulator to estimate the efficiency of
its foundation. Although JXTA’s peer group is
our algorithm. The achievements of our previ-
secure and capable to act in ad-hoc environment,
ous research were published as a set of proceeding
some investigation[96] tells current JXTA imple-
papers[136, 137]. We will examine the optimal
mentation has limitation on data transfer. Thus
combination for various situations in our future
it may have performance bottleneck, mainly due
experiments.
to its complexity.
l
r
e
p
t
middleware,
r
contemporary
JXTA[273] uses the idea of peer group as
o
A
We are now continuing to experiment using our
a
This report’s contribution is in rendezvous pro第 5 章 Peer Group Rendezvous Using Intersection
among Peer Groups on DHT
Rendezvous
is the process to find nodes to communicate.
It includes service based, interface based, time
a
n
n
u
cess using concept of peer group.
based, and free keyword based rendezvous.
0
variety of node characteristics, rendezvous in large
5.1.1 Motivation and the problem
scale is important and should not be overlooked.
Peer group is a strong and flexible structure to
We have been making rendezvous with DNS,
enable coordination between applications, server-
search engine, and some of service location or
client, and peers in networks. The idea of peer
directory service. But they seldom scale, or just
give us simple name binding like DNS, or just
cover major content like search engine.
E
J
but on the Internet we are still unable to use
O
the concept in large area, large group, and interadministrative domain.
Fig. 5.1 describes segment map of such rendezvous technology.
A peer means an equivalent node.
In this
The x-axis is local-global attribute. In local
W
I
D
E
P
group is originally introduced in IS-IS toolkit[14],
R
C
T
2
5.1 Background
0
3
Due to rise of number of Internet nodes and
Fig. 5.1. Segment map of rendezvous technology
378
W
I
D
E
P
R
O
J
E
C
rendezvous, candidates of rendezvous are limited
With the power of the bridges, we are able to
to nodes in the same domain with rendezvous
feel and control physical from virtual communi-
user. The domain means local segment or local
cation. To enable the power to the most extent,
administrative domain.
a user needs the ability to select a set of nodes
The y-axis in the figure represents micromacro attribute. Macroscopic rendezvous mean
server/service centric rendezvous.
T
out of trillions of edge nodes, to accomplish user’s
objectives.
Usually,
For example, a user may want to find specific
server/service does not plug and unplug as regular
temperature sensor in a room at distant location
client does, or many nodes could form a service for
and foreign administrative domain. If local ren-
redundancy. Target of macroscopic rendezvous is
dezvous system is used, the user’s query does not
service, not a node.
go over one administrative domain.
Microscopic rendezvous is a node centric
Thus, global-microscopic rendezvous is needed.
method. What a user wants is the printer in that
Legacy and recent ubiquitous systems like
room, the sensor node on the coffee pot there, or
STONE[188] tend to focus on micro-local ren-
just the PC ahead of the user.
dezvous. Their focus is in single domain like a uni-
As the map tells, we have global-scale tech-
versity campus. Actually, we need to intercon-
nology like UDDI and microscopic technology
nect very far edge nodes as same as local edge
like Service Location Protocol (SLP)[93], Univer-
nodes.
sal Plug and Play (UPnP)[303], and Rendezvous
The map also tells there is no major rendezvous
dezvous. Actually, to empower the edge nodes in
ubiquitous computing environment, technology in
why global-microscopic rendezvous is needed.
5.1.2 Rise of edge
Legacy network communication is based on
virtual-virtual communication. A manager puts
their content on a virtual space (e.g. a web server)
and virtualized people (physical location is not
relevant in communication) through a WWW
browser watch them.
Rise of edge is both capacity and capability
improvements on the edge nodes placed in user’s
space, not in server room. Especially in semantics
of ubiquitous computing, edge nodes like displays,
sensors, and web-cams have interface between
real space circumstances. They even have ability to control real space attributes like lighting
controller, audio/video system, or air-conditioner.
These nodes are bridge between physical world
and virtual world.
the following:
24
Definition of rendezvous:
The process to find a set of nodes k out of universal set U . Node characteristics list c distinguishes k from U − k.
The definition tells that rendezvous process
occurs around node characteristics. Node characteristics include interface, class, location, timelocation, and keyword. In practice, characteristics
must be represented as some data, like arbitrary
string, value, object, or document. In this report,
the author assumes that a characteristic is represented as a key string. For example, printer
should be represented as “printer”. Namespace
management of the key string is not discussed
in this report and the author assumes everyone
shares a de-facto dictionary space.
Interface based rendezvous is the process to
find nodes with data I/O capability of certain type. Exported interface object class definition of remote method invocation would be
a good characteristic for the rendezvous. Prim379
Integrated Distributed Environment with Overlay Network
the segment is needed. The next section describes
In this report, the author defines rendezvous as
●第 部
technology to accomplish global-microscopic ren-
5.1.3 Rendezvous
24
technology by Apple Computer Inc.
w
●第 24 部 Integrated Distributed Environment with Overlay Network
itive type of such rendezvous is MIME file type
is handling of complex queries. In their work,
like text/html or image/jpeg, but MIME file type
a resource is described in tree and the tree is split
alone does not tell how the I/O will be handled.
into strands. The strands resolved in parallel thus
In this report’s method, an infrastructure node
like “LBP-...” Those values will be set in the fac-
takes care to make efficient intersection between
tory.
each peer group (corresponds to each strands) and
Location would be another characteristic.
For example, free string like “Building #60
Third Floor” and lat-long combination like
traffic between each infrastructure node would be
reduced.
p
t
node service class like “Printer” or product class
r
a complex query make a fair amount of traffic.
o
Characteristics of class based rendezvous is
5.2 Rendezvous with peer groups
There are many characteristics to be a ren-
sion to location-based rendezvous is time-location
dezvous point (key) as section 5.1.3 describes. To
a
represents an activity in certain place. A confer-
support all of them, infrastructure systems should
u
ence would be represented as “2003/10/01 10:00-
have free characteristics notation. In addition,
16:00 @ Conference Room B”
a set of node should be able to be bound on each
n
In addition, free keyword based rendezvous
a
should be available to accommodate new and
3
innovative application. Like file share rendezvous,
0
l
r
resenting location characteristics. Natural exten-
n
e
“N140.330E38.994” would be good candidate rep-
streaming radio listener rendezvous, and so on.
consists of a peer group.
Thus, peer group concept is a natural solution
to support such a free rendezvous, as peer group
0
concept itself does not introduce any model like
5.1.4 Related Research
service class, interface, and location.
Work of Reynolds and Vahdat[238] makes effi-
In this section, the author proposes a model of
cient keyword searching over DHT. Their method
peer group with i3. An extension is proposed to
enable flexible set operation on the infrastructure.
E
to produce intersection of keyword-bounded table
J
using bloom filter is close to method described in
O
C
T
2
characteristic. A set of nodes for a characteristic
this report.
R
Internet Indirection Infrastructure[270] is an
filter technology is to control false positive rate.
infrastructure to enable indirect communication
A false positive is not failure in rendezvous case
among Internet nodes. The base of the infrastruc-
described in section 5.2. It results in excessive
ture is DHT like Chord[271]. And each hashed key
traffic only. Thus, certain amount of false posi-
represents a “indirect socket” for one-way commu-
tives is acceptable and this approach does not re-
nication.
W
I
D
E
Contribution of this report’s approach on bloom
P
5.2.1 Internet Indirection Infrastructure
check result by transferring actual data between
A listener node that wants to listen to certain
key inserts the node’s contact like IP address/port
DHT nodes.
In addition, as this approach does not need
pair on the key. A sender node that wants to
transfer of actual content, parallel query among
send a message to the key injects the message into
three or more target keyword/peer group is done
a node of the infrastructure. With algorithm of
in simple way. Query of A ∩ B ∩ C could be sep-
DHT, the message is routed to the DHT node that
arated to query of X = A ∩ B and Y = A ∩ C, on
is authoritative on the key. Finally, the authorita-
a node that holds set A. Query for X and Y is
tive DHT node sends the message to the listener
independent and simple parallel strategy works.
node.
The proposed rendezvous method is something
similar to INS/Twine[9].
380
The major difference
There may be more than one listener node at
the same key. In the case the key is multicast key
W
I
D
E
P
R
O
J
E
C
T
Fig. 5.2. A model of peer group rendezvous
and the message sent to the key duplicated and
tradeoff and reduces traffic needed for the oper-
forwarded to all the listener nodes.
ation.
5.2.2 Proposed peer group rendezvous with
5.3.1 Get-intersection operation and bloom
filter
On rendezvous process, a seeker node (client)
This method contributes to traffic reduction
wants to find a set of nodes with specific set
on get-intersection (X ∩ Y ) operation. For ren-
of characteristics. After finding, the client node
dezvous purpose, make smaller and finer grained
would want to send query to the set to find best
set as k is needed. Thus, intersection is more
node to use.
important than union.
One characteristic for one peer group approach
There are local and remote peer groups to be
is natural approach to make such a rendezvous.
handled. Get-intersection operation is performed
The client wants complex resource and issues com-
on a node in the DHT. Request for the operation
is routed to DHT node that holds one of groups
under the operation. The selected group is on the
ment in this case is a characteristic.
node and this is the local peer group. Others are
In this report, the author proposes a limited set
nodes over DHT in most cases.
a complex query. Complex queries may be pro-
Sending and fetching whole peer group data
cessed in various ways. In this case, each element
to get intersection among local and remote peer
is list of node identifier or contact. Handling each
group costs too much. With get-intersection oper-
list as set and applying set operation is simple and
ation, the entries wanted are in the local peer
effective way to solve the query. For example, the
group. Thus, the local node does not need whole
query X and Y and Z is converted into X ∩ Y ∩ Z.
remote group. It just needs to know if each entry
The Fig. 5.2 represents simplest peer group rendezvous.
is in the remote group.
The seeker node gets c because the
The operation is accomplished using exchange
infrastructure knows X, Y , and Z with DHT, and
of bloom filter[18], without sending any of entries
can get intersection among them. Actually, the
in the group. Bloom filter is a method to find if
infrastructure forwards the given message to peers
a data is in the data set or not, with possibility of
in the intersection, and those peers can contact
false positives.
the client to serve.
5.3.2 Bloom filter and false positives
5.3 Simple set operation on peer group
A bloom filter is array of bits created with arbi-
To enable flexible rendezvous mentioned above,
trary length L, and a set of entry is registered to
the author proposes a method to make get-
the filter. With a filter with the registered set,
interaction operation over DHT nodes.
an entry can be tested against the filter. The test
The
operation protocol accepts allowable errors as
24
remote peer groups because they are on remote
returns positive or negative as result.
381
Integrated Distributed Environment with Overlay Network
operation, get intersection, as operator to make
●第 部
plex query like X and Y and Z. Each element like
X in the query must be atomic, and atomic ele-
24
DHT
w
●第 24 部 Integrated Distributed Environment with Overlay Network
Bloom filter test suffers from false-positives. If
case, set A is the local peer group and set B is
a test returns negative result, there is no chance to
the remote peer group, and SA is local node and
have the tested entry in the registered set. On the
SB is remote node. Note that SA can find address
other hand, positive result of a test does not guar-
of SB from B’s hash value with DHT mechanism.
antee the entry in the registered set, due to hash
1. at SA: sends number of entries of set A (|A|),
value conflict used in the filter algorithm. False
t
set.
and required phase p, to SB.
2. at SB: calculate bloom filter of B from M =
|A| + |B| and given p. Return it to SA.
3. at SA: tests each entry of set A on the filter,
In case of false positives, excessive traffic is pro-
and assume entries with positive result as the
p
o
tive result on testing an entry not in the registered
r
positive rate (FPR) is the probability to get posi-
intersection.
The trick in the protocol is control of FPR. SA
tion among groups in query. In the case, a false
sends number of entries to SB. Thus, SB can use
a
positive means a message forwarded to an unex-
|A| + |B| as parameter M .
pected peer.
n
n
This section describes a prototype to investigate
a
tive rate should be balanced against message size.
correctness of concept. In addition, basic anal-
Detailed analysis of excessive traffic due to false
ysis of the proposed model and set operation is
positives is described in section 5.4.2.
described to support the investigation.
2
0
intersection operation. Thus, expected false posi-
3
5.4 Proof of concept
Low traffic is outcome of bloom filter based get-
0
l
r
sent from client to peers that belongs to intersec-
u
e
duced. The infrastructure forwards the message
The following equations tell the false positive
rate under certain condition[18].
• f = s and L =
5.4.1 The prototype
C
– L: length of the filter
– M : number of elements in candidate set.
The candidate set is set of elements that
Chord node uses only 159 finger connections per
may be tested against the filter.
node at most, thus the prototype keeps connec-
R
– f : False positive rate (FPR)
E
The base of the prototype is Chord-like DHT
J
p·M
−(log s)
O
T
p
P
– p: phase, number of independent hash func-
add-on. It is written in about 3500 lines of Python
code.
It uses TCP for all communication.
A
tion open for each finger node. The query resolution process is iterative. If the answering node
– s: saturation. rate of 1 (true) among all
knows better DHT node to ask, it returns redi-
filter bits in case of all of candidate elements
rection message. The query issuer retries on the
registered. The literature[18] tells a filter is
new node and repeats the process until the query
most effective if s = 0.5
resolves. The wire-format of protocol is serialized
W
I
D
E
tion used to select a bit in the filter.
with message forwarding on and get-intersection
Thus, to define appropriate length of L in the
best efficiency (s = 0.5), we need to know required
FPR (f or p as s is static) and M .
form of Python language object for now. Thus
object serialization overhead exists.
Each entry in the DHT is an array. Inserting
something on the entry appends the value on the
5.3.3 Protocol of get-intersection operation
array. The message-forwarding module to listener
Get-intersection operation for the query A ∩ B
node works if the listener node inserts data with
is processed between a server (SA) that holds
handler format.
set A and a server (SB) that holds set B is as
The format consists of format ID string and
the following. A query is processed on the node
endpoint tuple. Endpoint tuple is host endpoint
that holds the first group in the query. In this
ID like DNS name or IPv4/v6 address, and port
382
W
number with 32-bit integer.
I
D
E
P
R
O
J
E
C
T
least filter for about 200 candidate elements with
A client resolver may send get-intersection
0.012 (200 × 6.1e−5) expected false positives or at
query. Query has a target hash ID, list of ID,
most filter for about 440 candidate elements with
and requested p as the payload. The query is
3.4 (440 × 7.8e−3) expected false positives.
routed to authoritative ode of target hash ID. The
Another evaluation is on M and size balance
node tries the get-intersection protocol described
between left group and right group of the inter-
in section 5.3.3 for each ID in the ID list, and
section operator.
return composed result (list of handlers) to the
tells, the filter length L is derived from p and M .
client resolver as the requested intersection.
But there is no consideration on the balance of
As equation in section 5.3.2
left/right. If left group has 999 records and right
operation
In this section, the author evaluates traffic
amount related to the method proposed.
Filter length As this method involves an integer (size of local set), an identifier (remote set
identifier), and bloom filter to find intersection,
the length of the filter itself dominates the whole
traffic volume.
Optimum filter length itself can be derived as
mum L against M is shown in Fig. 5.3.
In the figure, there are three lines corresponds
(p = 10, f = 9.8e−4) FPR case, and less than 0.01
percent(p = 14, f = 6.1e−5) FPR case. Two horizontal lines are 512 bytes (guaranteed payload size
the filter with M = 1000, spends 181 bytes per p,
if the record is small enough.
Let length of a record be r, and the following
equation tells when filter costs more than sending
back the whole group.
m=p·
1
−(log 0.5) · r
m is efficiency ratio of the bloom filter. If m is 1,
the filter transfer and whole group transfer are of
the same cost. In contrast, if m is 0.01, the filter
transfer costs as much as one percent of whole
is worth 0.9 percent of whole group. If the right
group only have 5 percent of whole set, sending
bloom filter with p ≥ 6 costs more than sending
back whole group.
of single UDP datagram) and 1460 bytes (com-
Excessive traffic amount due to false pos-
mon size of largest datagram in Ethernet, without
itives: As an intersection of groups is target
fragmentation). According to the equation and
of a message sent from a client, a false positive
the figure, a 512-byte UDP message can carry at
results in an excessive message forwarded.
As
the peer selected by false positive may just ignore
the message, drawback of false positive is just the
message transfer cost.
Let the message size be m and size of local
peer group be Ml . Then, expected excessive traffic caused by a get-intersection operation (Te ) is
Te = sp · Ml · m. At the same time, L is decided
on p and M . Thus, as m, Ml , and M given,
a node can find the best p with the lowest transfer
Fig. 5.3. Relation of filter length and number
of elements in candidate set
24
group transfer. For example, if r = 160, one phase
amount (L + Te ).
The protocol proposed in the section 5.3.3
383
Integrated Distributed Environment with Overlay Network
to less than 1 percent (p = 6, f = 7.8e−3) false
positive rate (FPR) case, less than 0.1 percent
group back to the left is cheaper than sending back
●第 部
we get M and p. According to section 5.3.2, opti-
group only have 1 record, sending the whole right
24
5.4.2 Evaluation of get-intersection
w
●第 24 部 Integrated Distributed Environment with Overlay Network
would be extended to let a node to find the best p.
Table 5.2. Number of messages among the
whole DHT
To make that, the required values must be on the
node. As a local node sends parameters to remote
#Groups
node, the remote node is the appropriate node to
r
o
p
e
following. First, it sets up the DHT nodes and
r
waits 30 seconds for the finger information to be
initialized. After the boot, a set of random keys
and values are created, series of combinations of
(key, value) are selected out of the keys and the
values, and the combinations are inserted to the
a
n
a
tion 5.4.1. Test preparation procedure is as the
u
measured with the prototype, described in sec-
n
Traffic volume and number of messages are
l
t
Traffic volume and latency in practice:
DHT nodes. In the following test scenario, there
10 groups at random.
get
all
get
i
get
all
N =5
11.3
11.5
20.8
23.4
N =8
12.8
12.5
24.1
25.2
N = 10
16.0
16.0
24.4
31.6
and a key corresponds to a group. A key holds
T
C
to a peer (bound to the value) joins to a group
(bound to the key).
result of get operation on all the groups (get-all)
is also shown.
The table tells that (1) the system looks to scale
better than O(N ) because sum of bytes on N = 10
is less than double of sum of N = 5, (2) getintersection consume less traffic. Especially for
four group case get-intersection consumes 42 per
cent of get-all, in contrast to two group case that
consumes 45 per cent of get-all.
exchange per operation for two groups intersection, four groups intersection and both get-all
on the same condition above. We can estimate
expected latency of each operation by expected
RTT among each nodes and the client.
If we
estimate average RTT as 200 milliseconds, get-
A test client makes get-intersection in succession among two and four groups. The operation
to get all the groups to make intersection on the
P
R
O
J
peers. A combination of (key, value) corresponds
E
one or more values as a group holds one or more
client side, get-all operation in short, at the same
intersection among ten nodes (N = 10) and four
groups (#Groups=four) may consume more than
3 seconds. Parallel query would help to make it
shorter.
D
Table 5.1 describes traffic volume involved in
I
condition is also measured for comparison.
get intersection operation (get-i) among two/four
W
E
5 nodes, 8 nodes, and 10 nodes. For comparison,
The table 5.2 tells average number of message
In the prototype, a value corresponds to a peer
2
0
0
3
are 500 peers and 100 groups. And a peer joins
Four
get
i
find the best p. To help it, m should be given
along with Ml to the remote node.
Two
groups, and the operation among four groups per
operation (average of 1000 operation), against
Table 5.1. Traffic Volume among the Whole
5.5 Discussions
5.5.1 Naming of groups
In this report there is no assumption and definition on name of group. This will cause confusion
on name space.
For example, consider printer group. Due to
DHT(bytes)
latitude of group name, you can make printer
#Groups
384
Two
Four
group in English, Greek, Dutch, or any other lan-
get
i
get
all
get
i
get
all
guage with every kind of encoding like iso-2022,
N =5
599
1177
983
2376
example is many encoding for one language. In
N =8
622
1491
1275
2887
Japanese, there are iso-2022-jp (JIS), EUC-JP,
N = 10
812
1760
1413
3483
Shift-JIS, and Unicode. DHT distinguishes every
iso-8859, Unicode, and others. More confusing
W
group named identically and encoded differently
as independent groups.
I
D
E
P
R
O
J
E
C
T
The scalability against huge group may be
beyond scope of DHT. Thus the method must be
The author considers two approaches to ease the
confusion.
integrated with other huge list handling method.
An approach for it is to set upper limit of num-
The first approach is to define precise naming
ber of nodes on each group.
The next node
convention by some de-facto or standardization
after the limit would replace a node in the group
process. This is simple and robust approach but
with LRU if possible. Another approach is mak-
some application does not wait until such names-
ing subgroup of huge group, with finer grained
pace is built.
granularity.
For example, “color printer” and
The second approach is some sort of collabora-
“monochrome printer” would be a good set of
tive filtering to find similar groups, with or with-
candidates as subgroup of “printer” group. Let
out external knowledge. If DHT node can assume
“printer” group be abandoned and move all the
group α and β is similar, it can automatically
printers into appropriate subgroup. The aban-
include reference to the other group when answer-
doned super group only includes reference to those
ing request. Then, client could select larger group
subgroups.
or just ask both (or all, if there are more than
matic integration of very similar group. If group β
5.5.3 Security consideration
DHT needs to be secured to be used for real
application.
nate β and all request on the group is forwarded
heavily on DHT, threats on DHT are threats on
to α.
the method.
Another consideration is name conflict.
If
many incompatible instant messaging application,
As the proposed method depends
Apparently, at least the following three denials
of service threats exist.
24
1. Spamming on DHT entries
name like “Beginner’s Room” or “Help Desk,”
2. Malicious DHT node
name conflict leads up to disaster.
3. Adding self to unrelated group to gain information
A new application which
If a peer group got DoS attack, the group
does not rely on other application’s names-
become useless because only junk would be found,
pace must put a pseudo-random data and/or
or more simple case no peer takes care of the
time-stamp ahead of the name.
group, during rendezvous process.
the group name.
For example,
“104956914.f96f;Beginner’s Room” for the appli-
Details of each attack and defense are beyond
cation that owns prefix “104956914.f96f;”
the scope of this report and not described here.
5.5.2 Handling huge group
5.6 Conclusion
DHT is a novel method to realize fully-
This report proposes a design of a simple peer
decentralized data table. Actually, characteristics
group rendezvous process. Introducing intersec-
of DHT are similar to hash table. It has simi-
tion between peer groups, the method can support
lar limitation on data handling with regular hash
flexible resource finding and rendezvous.
table.
The peer group rendezvous method proposed by
Proposed rendezvous method is based on distributed hash table (DHT) technology.
There-
this report assigns a hash entry for a group. The
fore,
hash entry keeps a set of peers as single list. Thus,
ship information is completely distributed and
the sets contain peer group member-
this method does not scale against group size.
cost of communication to make set operation
385
Integrated Distributed Environment with Overlay Network
online game and other application use the same
A solution is to mandate namespace tag in
●第 部
is similar with α, DHT infrastructure can elimi-
24
three). More advanced approach includes auto-
w
●第 24 部 Integrated Distributed Environment with Overlay Network
(get-intersection) is the key factor of the method’s
both transactions in the application network and
efficiency.
i-WAT network.
to find out the intersection. The length of bloom
be utilized in real application like i-WAT and
filter is controlled by the whole size of those two
other networks to step towards multi thin over-
groups to get intersection. Thus, there is no need
lays network architecture.
to verify the result as long as the user accepts the
false positives under certain rate.
6.1 背景
The author also points out some difficulties to
インターネットの普及とともに、その利用法の幅
deploy proposed peer group rendezvous method.
は広がりつづけている。特に、IP アドレスで表現で
Security, naming, and group size issue should be
きない資源を識別・表現するために、オーバーレイ
solved as the next step.
ネットワーク(以下オーバーレイ)等さまざまな方
l
r
e
p
o
t
With this article we have discussed what is
requirement for URP. As the next step it should
r
To reduce the cost, this report also proposes
get-intersection protocol that sends a bloom filter
第 6 章 Uniform Rendezvous Pointer
n
u
a
法が考案されている。一方で、それらの協調動作の
n
オーバーレイネットワーク間相互参照のた
a
めの識別子空間
ても限定的な解である、という問題がある。
本章では、インターネットを用いて「統合分散環
境」を実現するために、これらオーバーレイ同士を
3
相互に接続する必要性について論じる。
0
Abstract
As the first step towards multi thin overlays
2
0
ための枠組がほとんど存在しないか、存在したとし
network architecture, we propose URP (Uniform
統合分散環境を、以下の 2 つの条件が成立する環
境と定義する。
1. 分散: 全世界を継ぎ目無く統合するネットワー
E
works. We discuss why we need URP and required
クが存在し、その上に無数の資源が存在する。
J
functionalities for it. Especially, we evaluate some
2. 統合: 存在する無数の資源が、人間の目的達成
O
topics like policies, ability of verification, and so
を補助するために有機的に統合され、機能を提
on.
供する。
The most significant difference between regu-
条件 1 は、IPv6 やネットワークアプライアンス等
lar URL/URI is that URP does not just iden-
の普及により達成されると考えられる。一方で、条
E
P
C
to point resources among different overlay net-
R
T
Rendezvous Pointer). URP is the identifier space
6.1.1 「統合分散環境」に向けて
件 2 は、ネットワークを構成する資源の数や種類が
a client should try search among overlay and
多くなるにつれて困難になる。
W
I
D
tify a resource. Instead, URP is notation how
how the result would be verified and treated.
条件 2 を達成するために、識別子による資源の表
Because resources on some overlay like Freenet
現能力に注目する。現在の Internet で多く用いられ
and Gnutella are unstable and have no identity,
ている識別子は、IP アドレス+ポート番号、そして
just identifier nor locator would sufficient in inter-
URL である。IP アドレスはネットワークインター
overlay.
フェイスの識別子であり、これにポート番号を付け
URP would be efficient glue between i-WAT
る事によってそのインターフェイスを持つ計算機上
overlay network and other collaborative overlay
に存在するプロセスを指定する。同様に、URL は特
network. With URP, overlay users can exchange
定のプロセスが管理するファイルの識別子である。
notes using i-WAT and other barter overlay net-
これらの識別子は、
「計算機上のプロセス」という
work as rewards of collaboration. In other words,
粒度に縛られている。あらゆる資源を表現するため
other application and overlays may use i-WAT
に、その資源を管理するプロセスを指定する必要が
network as a market and URP is used to link
ある。一方、
「実世界の人間」や「地理的な位置」等、
386
W
特定のプロセスに強く関連づけられない種類の資源
が次々とネットワークに登場しつつある。
I
D
E
P
R
O
J
E
C
T
現状では、異なるオーバーレイ上の資源を組み合
わせて活用する事には困難がある。一方で、「自由
また、必要な資源を効率的に発見するためには、資
で創造的なランデブー」はこの困難を乗り越えた先
源の特徴的性質を記述できる識別子空間が必要とな
にある。また、資源の選択がオーバーレイの内部に
る。その空間は一意に定義できるものではなく、発
閉じていると、「全ての要求を満たすオーバーレイ」
見の目的に応じて異なる空間が設計される。実際、
を作らなければ目的は満たされない。複雑な目的の
単純な名前、資源の性質やサービスインターフェイ
達成に向けて、単一の目的で作られたオーバーレイ
ス、セキュリティポリシーや匿名性等、目的に応じ
をモジュール的に組み合わせる事で、自由かつ創造
て異なるシステムが作られている。そして、システ
的な資源の組み合わせを実現でき、かつ価値創造が
ムの数だけ識別子空間は存在し、互換性は無い。
オーバーレイの内部に閉じないので、自発的に多数
の応用が生まれるものと考えている(6.3.5 項)。
6.1.2 オーバーレイ
オーバーレイをまたがる抽象ノードの統合的利用に
オーバーレイは、多様な識別子空間を実現するため
向けた最初のステップとして、様々なオーバーレイ上
の一つの手段である。IP を基礎にしたインターネッ
の抽象ノードを指し示すための識別子空間、Uniform
ト上に、アプリケーションが必要とする識別子空間
Rendezvous Pointer(URP)を定義する。
を実現し、その上で資源への到達性を実現する。
6.2 複数オーバーレイの統合に向けて
レゼンスといった資源の表現のために発達している。
より得られる具体的なシナリオについて紹介する。
一方、Tenbin[347] 等は、コンテンツという資源を扱
その上で、複数オーバーレイ利用のモデルを定義し、
う。Chord[271] 等の分散ハッシュテーブル(DHT)
モデル中に存在する資源を一意に識別するために必
は、ハッシュ値という抽象的な資源の表現を扱う。
要な機能を考える。
URP に対する要求は、複数のオーバーレイにまた
用を主目的としたものなどもある。なお、本章では
がる文脈において、それぞれのオーバーレイにある
オーバーレイ上のノードと区別するため、インター
資源を区別し、指定できる事とする。
ネット層におけるノードを IP ノードと表記する。
目的の数だけ資源の抽象化の手法は異なり、その
結果多数のシステムが生まれている。本章では、こ
れらのシステム全てを「オーバーレイ」という枠組
で捉える。オーバーレイは、IP アドレスで表現でき
ない資源を抽象化して取り扱い、資源への通信機能
を提供する。
6.2.1 複数オーバーレイのモデル
複数の異なるオーバーレイを利用するモデルを考
える。
オーバーレイには、様々な手法で抽象化された資
源が独立・並列に存在する。
資源は一意に指定できない場合がある。例えば
Freenet では、検索を開始する場所によって得られ
6.1.3 オーバーレイ相互接続の要求
オーバーレイ上に抽象化された資源は、ネットワー
る内容が異なる。この場合、資源を示す代わりに資
源の探し方を指定する他ない。
クを経由して利用可能である。これを抽象ノードと
オーバーレイは、IP ノード同士が結合して構成す
呼ぶ。しかし、抽象ノードとして利用できるだけで
る。この構成方法にはいくつかのパターンが認めら
は統合分散環境には不十分であり、これら資源を統
れる。
合する(6.1.1 項条件 2)必要がある。ネットワーク
1. 既定の初期 IP ノード(well-known bootstrap
の価値を高めるには、目的達成のために最適な資源
nodes)のみで情報共有し、他の IP ノードはク
を自由かつ創造的に選び取り、要求を満たす資源の
ライアントとして構成
組み合わせを選択する必要がある。この資源選択の
2. 既定の初期 IP ノードを中心に自動構成
自由を提供する機能を「自由で創造的なランデブー」
3. 近隣の IP ノードとの自動構成
と呼ぶ。
4. システム外の経路(Out of Band)によって隣
387
24
Integrated Distributed Environment with Overlay Network
他、Freenet[39] 等、IP ノードに対する匿名性の適
●第 部
本節では、まず複数オーバーレイを統合する事に
24
各種インスタントメッセージングシステム(Jab-
ber[141] や ICQ[109] 等)や IRC[145] 等は、人やプ
w
●第 24 部 Integrated Distributed Environment with Overlay Network
接 IP ノードを手動構成
5. DNS 等のディレクトリサービスへの依存により
構成
手法 1 および 2 は、既定の初期 IP ノードをネッ
トワーク構成の足掛かりとする。参加する全ての IP
ノードは既定の初期 IP ノードを知っており、それら
URP は、多様なオーバーレイ上に抽象化された抽
象ノードを指し示す。抽象ノード利用には指し示す
だけでは不十分であり、抽象ノードに対してどのプ
ロトコルを利用するか指定できる必要がある。
従 来 の URI 式 の 数 文 字 の プ ロ ト コ ル 識 別 子
t
精密にプロトコルを示す指摘方式が必要な場合があ
た自動構成手法である。Apple Rendezvous ではこ
る。例えば、Jini の様に、抽象ノードにアクセスす
の手法を利用している。
るためのスタブクラスの定義により資源を抽象化す
r
e
p
手法 3 は、リンク層ブロードキャスト等を利用し
r
(chord、freenet 等)による指定方式の他に、より
o
IP ノードの利用が前提となっている。
6.2.2.1 アクセス手段の指定
手法 4 は、一部の Gnutella 由来のシステムで利用
る場合等がある。
される手法である。IRC や HTTP によって初期 IP
6.2.2.2 ポリシー情報の提供
a
a
u
n
立したオーバーレイが多数発生する(手法 2、3)の
か、という違いがある。本章では、前者をユニバー
3
られる。
サルネットワーク、後者をコミュニティネットワー
0
の初期 IP ノードや物理リンクに関連づけられた独
クと呼ぶ。また、コミュニティネットワークにおけ
0
ネットワークへの参加の際、アイデンティティを
示す必要や、資源の提供を求められる場合等が考え
るそれぞれの断絶したオーバーレイをコミュニティ
2
構成方法によって、全世界で共有されるネットワー
クが一つできる(手法 1、2、5)のか、それとも特定
n
l
ノードを別途取得してネットワークを構成する。
と呼ぶ。
このような場合、IP ノードはポリシーに基づいて
振舞うべきなのか知る事により、事前に資源を用意
できる。また、ポリシーに従えないのであれば、無
駄なアクセスのための時間・帯域の消費がなくなる。
6.2.2.3 コミュニティの指定
例えば、オンラインゲームのためのオーバーレイ
異なる要求を行う可能性がある。具体的には、ただ
は、規模性やプレイヤーの快適性等を考えて、複数
の「ワールド(=コミュニティ)
」を持つ場合がある。
E
乗り(free riding)を防ぐために何らかの帯域制御を
J
行う、サービスに対価を要求する、認証を要求する、
O
あるいは匿名性を保証するなどといったポリシーで
抽象ノードが属するコミュニティを指定する必要が
R
ある。同一のオーバーレイに複数のポリシーが混在
ある。コミュニティを示すには、初期 IP ノードの
P
C
T
コミュニティやオーバーレイは接続者にそれぞれ
する事も有り得るし、ポリシー毎に異なるコミュニ
IP アドレスを示す等の方法がある。
このような状況下で抽象ノードを識別するには、
E
ティを形成する場合もある。
W
I
D
当然、ネットワークサービスである以上、共通の
プロトコルを利用する事は大前提となる。
以上、本章では、オーバーレイを以下の 4 要素に
整理したモデルを考察の基礎とする。
6.2.2.4 依存/外部参照の指定
オーバーレイは他の情報に密に結合している場合
がある。例えば、特定の地域に存在する抽象ノード
群を抽象化したオーバーレイを考えた場合、地域を
1. 抽象ノードの抽象
指し示す記述から正しいコミュニティを選択する事
2. ネットワーク構成/コミュニティ
になる。このような場合、初期 IP ノードを外部の
3. ポリシー
ディレクトリサービス、例えば DNS や DHT などを
4. プロトコル
利用し発見する。そのための手掛りを URP に含め
られると良い。
6.2.2 資源指定方法の考察
本項では、前項で述べたモデルにおいて資源を指
定するための方法について、どのような場面でどの
ような指定方法が必要になるか考察する。
6.2.2.5 資源成立条件の限定
あるオーバーレイにおいて、時間経過した後もそ
の内部の資源が有効である保証は無いし、オーバー
レイのどの IP ノードから資源探索しても同じ資源
388
W
に到達する保証も無い。
資源の有効性や同一性を確認するためには、資源
I
D
E
P
R
O
C
T
• identity: アクセス者のアイデンティティ
が意味を持つための条件を示す方法がある。識別子
に有効期限を与え、その期間のみ有効性を保証する
• preference: ポリシー要求等
確認する方法などが考えられる。
E
「どのように探索するか」:
• condition: 資源探索成立の条件
方法や、MD5 チェックサムによって内容の同一性を
J
資 源 を 同 定 す る た め 、最 低 限 、accessor、
community、resource id が必要である。「どのよ
うに探索するか」は必要に応じて利用すれば良い。
6.2.2.6 ユーザ識別子の記述
特定のオーバーレイに対して、
「何者として」アク
セスするのかを指示する識別子は、アクセス制御を
簡略化できる。
6.3.3 表記案
URL の表記方法に則り、基本形は以下のように提
案する。
{accessor}://{community}/{resource id}
6.2.2.7 Uniform, not Universal
URP は、全世界(Universal)の資源を統一的に
表現するものではない。ある特定の環境においての
み意味を持つ識別子、文脈に応じて示す資源が変わ
る識別子が存在する事を許す。
一方で、URP はどのような環境においても画一的
(Uniform)に生成・解釈できる必要がある。
また、全ての要素を記述するために、以下の表記
を提案する。
{accessor}://{identity}@{community}
?{condition}!{preference}/{resource id}
(改行は含まない)
URP の各項目について以下に述べる。
「何を利用して探索するか」: accessor は、資源へ
のアクセス方法を規定する。アクセス方法の規定に
中で抽象ノードを識別し、かつオーバーレイの多様
さを柔軟に吸収できるポインタを提案する。
は (1) 明文化されたプロトコルによるアクセス (2) 抽
象クラス定義によるアクセスの 2 通りが考えられる。
明文化されたプロトコルによるアクセスへの
行う(例: chord can iwat 等)。
6.2.2.5 項での議論にあるように、オーバーレイ上
一方、
「抽象クラス定義によるアクセス」は、未知
の抽象ノードは一意に特定できる場合もあれば、そ
ないしアクセス方法が一定しない資源への accessor
うでない場合もある。従って、URP は抽象ノードの
を提供する。URP によって表現される資源の利用法
位置を直接示す事を前提にできない。この制約下で
はある程度抽象化できる可能性がある。例えば、get
抽象ノードを示すために、抽象ノードの探索方法を
や put 等の基本的なデータ操作がある。このような
示すという方法が利用できるべきである。
抽象化されたデータ操作を、抽象クラスとして共有
従って URP は、
「探索方法」を示す事により抽象
ノードを指示する識別子である、と言える。
した上で、資源への accessor としての具象クラス
をネットワーク経由で供給できる。抽象クラスの定
義については 6.4.6 項で議論する。
6.3.2 要素の検討
ここまでの議論に登場した、オーバーレイの要素
を整理すると以下のようになる。
「何を利用して探索するか」:
• accessor: プロトコル識別子
「どこを探索するか」:
• community: 初期 IP ノード/外部参照
「何を探索するのか」:
• resource id: 実際の資源を識別する記述
「どこを探索するか」: community は、オーバーレ
イに接続するために必要な情報である。内容はオー
バーレイの構成方法(6.2.1 項参照)によって異な
る。既定の初期 IP ノードを持つ場合は空欄で良い
し、DNS 等の外部参照を利用する場合はその参照に
必要な式ないし名前を記述する。
「何を探索するか」: 各オーバーレイ内部で、資源
を示す識別子である。オーバーレイに対応して、抽
389
Integrated Distributed Environment with Overlay Network
ftp 等の scheme と同様、短い識別子による記述を
6.3.1 URP により示されるもの
24
accessor は、従来の URL における http あるいは
24
ここまでの議論を受けて、複数のオーバーレイの
●第 部
6.3 提案する URP
w
●第 24 部 Integrated Distributed Environment with Overlay Network
象ノードの識別子、ファイル名、問い合わせ文字列
等が書かれる。
「どのように探索するか」: identity は、{userid}:
{credential}、あ る い は{userid}の み に な る 。
userid は各オーバーレイ固有のユーザ識別子であ
る。credential は、識別子に対応づけられた秘密
r
o
e
資源をどこまで提供するかここに記述できる。例え
ば、利用する通貨単位が mh(Man Hour)だった場
合、condition に cost<0.4mh として記述する事で、
URP による資源探索は 0.4 mh 以下で終了しなけれ
a
n
u
域通貨・資源等)が要求される場合がある。それら
n
また、URP による資源探索プロセスに対価(地
r
のように記述する。
l
として URP に含める場合は、md5sum=16136a7....
a
例えば、ファイルの MD5 チェックサムを condition
p
t
である。
ばならない(さもなければ中断)
、という記述が可能
3
0
側に選択肢がある事柄について記述する。例えば匿
名性が実現可能なネットワークでは、利用者が匿名
2
preference には、資源を探索する際、資源利用者
0
になる。
T
易な資源利用を促すことができる。
ま た 、自 発 的 な 資 源 の 提 供 を 意 味 す る 記 述 も
preference に適当だろう。
6.3.4 提案する URP によるモデルの充足
P
R
O
J
E
URP においてこういった選択肢を記述する事は、簡
C
であるか無いかを選択できる。探索方法を指定する
E
I
考察する。
まず、オーバーレイの構成手法(モデル要素 2)に
W
て、提案する URP は必要な資源を指し示せるかを
D
6.2.1 項で述べた複数オーバーレイモデルに対し
ついて考える。ユニバーサルネットワークではオー
バーレイの構成のために必要な情報は既定のものと
して与えられるため、URP の記法に関わらずネット
ワークを構成可能である。一方、初期 IP ノードが必
要なコミュニティネットワークでは、community よ
り初期 IP ノードを伝達できる。
ネットワークのポリシーの記述(モデル要素 3)
は、preference あるいは condition によって行う。
preference は、計算資源の提供や匿名性など、確定
的な意思を記述し、condition はファイルのチェッ
クサムや支払える対価など、条件を記述する。
390
プロトコルの記述(モデル要素 4)は、accessor
によって行う。accessor は同時に、抽象ノードの抽
象(モデル要素 1)を定める。chord にとって、抽
象ノードは単なるデータであるが、通貨取り引きの
ためのプロトコルを利用する場合は、通貨あるいは
取り引きを行う者を抽象する。
しかし、accessor によって抽象ノードの抽象とプ
ロトコルの両方を定めて良いかについては、議論の
余地がある(6.4.6 項)。
6.3.5 具体的応用例
ファイル共有を行うオーバーレイは多数存在する。
それらには、ファイルを共有するためのコスト(HDD
領域・通信帯域・CPU 時間・電気料金等)や独自の
コンテンツの提供に対するインセンティブが乏しい
という問題がある。このようなオーバーレイを、こ
こではファイル共有オーバーレイと呼ぶ。
インセンティブの問題を解決するために設計され
た Mojonation では、内部にファイル交換と対価の
支払いの仕組みの両方を持つオーバーレイを構築し
た。ファイル公開や交換のための資源の提供に対し
て対価の支払いを求める事によって、より質の高い
資源の提供を促進するという狙いであった。しかし、
この統合されたシステムは普及に困難があり、オー
バーレイとしては成功しなかった。結局、対価のや
りとりをあるオーバーレイの内部のみで行う事によ
り価値創造をその中に限定してしまい、インセンティ
ブとして成り立たなかったものと考えられる。
これに対して、対価のやりとりを行うオーバーレ
イをファイル交換オーバーレイと結合させて利用す
るというアプローチが考えられる。例えば、対価の
一つとして「手形」のような地域通貨を扱うオーバー
レイ [250] が存在する。このようなオーバーレイを
ここでは対価交換オーバーレイと呼ぶ。
この 2 つのオーバーレイを統合して利用できれば、
ファイル交換と対価の支払いを対応づけを行う事は
容易である。例えば、先行して普及すると考えられ
るファイル交換オーバーレイに対して、対価交換オー
バーレイを扱えるプラグインソフトを導入する。対
価交換オーバーレイにおける相手の信用に関する問
い合わせや価格の擦り合わせ等の情報を、ファイル
交換オーバーレイ上で URP により交換する。URP
によってこのプラグインソフトが呼び出され対価交
換が成立する、といったシナリオが考えられる。
W
I
D
E
P
R
O
J
E
C
T
の直接即時的な連携が考えられる他、より大きな規
模での連携を考える事もできる。
例えば、URP を収集する検索エンジンのクロウ
ラー(収集プログラム)を考えてみよう。ある曖昧
な検索式に応じて、具体的な「資源の探し方」のリ
ストを提供する検索エンジンは、多様なオーバーレ
イの中に資源が抽象化されて存在する世界の利便性
を確実に向上させる。
また、URP により、異なるオーバーレイ中に表現
図 6.1.
ファイル交換オーバーレイと対価交換オー
バーレイの URP による統合(模式図)
された抽象ノードの羅列を表現できる。具体的には、
インスタントメッセージングにおける友人リストの
ようなものに、AIM、MSN Messenger、Jabber 等
図 6.1 は、このシナリオの模式図である。2 人の利
の利用者を URP によって表現し、格納でき、また
用者が、ファイル交換オーバーレイと対価交換オー
単一のクライアントプログラム(あるいは他のプロ
バーレイを同時に使用して、ファイルの交換と対価交
グラムを駆動するメタ・プログラム)に対して URP
換を URP によって対応づけている様子を示してい
を渡す事で、適切なプロトコルでメッセージをやり
る。対価交換オーバーレイはファイル交換オーバー
とりできる。
このように、URP によって、オーバーレイに存在
する「囲い込み」を乗り越え、オーバーレイ選択に自
URP により価値創造の領域が広がり、交換される
由と柔軟性を導入できる。筆者らは、この自由と柔
対価をインセンティブとして機能させる事が容易に
軟性は、ネットワーク環境を「統合分散環境」に進
なる。
めるために必須の性質の一つであると考えている。
このように、単独のオーバーレイで全ての仕組み
を実現するのではなく、自由で開かれた、創造的な
24
6.4.3 議論:「秘密の共有」の崩壊
匿名掲示板などを「コミュニケーション」の切口
レイをモジュールとして連携させる事により、応用
で分析すると、そこには「秘密の共有」と「自己顕
が自己創出的に発展していく事が期待できる。
示」という二つの側面が出てくる。特に秘密の共有
は、自己と相手の心理的な相互信頼を確立するため
URP により、オーバーレイ等の利用法、あるいは
の手段となっている。コミュニケーションを目的と
するオーバーレイでも同様である。つまり、URP が
オーバーレイによる通信アーキテクチャにどのよう
指し示すような資源を発見する事に価値を見いだし、
な影響があるか、以下に考察する。
発見した者を「仲間」として迎え入れるような人的
コミュニティの形があるかもしれない。
6.4.1 利点: 記述の容易さ
こういった人的コミュニティにとって、URP のよ
URP により、オーバーレイへのアクセス方法の
うな簡易なアクセス手段の記述は、共有される秘密
記述が容易になる。ユーザの目に見える範囲では、
へのアクセスを容易にし、相対的にその秘密の価値
メールや口頭での通知等が容易に行える。実際のア
を下げるのだろうか。
クセスを行うプログラムがアクセス方法を判断すれ
ば良いため、利用者に対する負荷が軽くなる。
また、URP により「検索」がオーバーレイに対し
ても可能になった場合の影響についても考察が必要
だろう。Google 等の検索エンジンによって、個人的
6.4.2 URP の応用可能性
なページやそのリンク集を経由した情報の探索(俗に
URP は複数のオーバーレイを連携させる事を目的
ネットサーフと呼ばれていた方法)は減少した。検索
として作られた。複数のオーバーレイによる連携に
エンジンは、URL によって無数の情報を発見し、検
は、6.3.5 項で述べたように、対価交換のような 2 者
索者に提供できるようになった。その結果、WWW
391
Integrated Distributed Environment with Overlay Network
ランデブーのための空間を用意し、単純なオーバー
6.4 議論: オーバーレイ統合に向けて
●第 部
価値は URP によって広く再利用できる。すなわち、
24
レイと独立に存在しているので、ここで交換された
w
●第 24 部 Integrated Distributed Environment with Overlay Network
上にひっそりと存在した人的コミュニティは一気に
いては、さらなる議論が必要である。
白日に晒され、その一部は公衆化する事を嫌い、あ
オーバーレイにおいては、様々な資源が様々な軸
るいはそもそも非合法故に WWW の外(ファイル
によって抽象化され、提供される。これら抽象化さ
共有ソフト等)に潜った。
れた抽象ノードに対する操作にはどのようなものが
URP によって、多数のオーバーレイが現在の
たインパクトを与えるのか等も考える必要があるだ
る。この場合、accessor としてプラグイン(あるい
ろう。
はスタブクラス)を用意する事で、ありとあらゆる
o
URP における資源の扱いを画一化できる可能性があ
t
一方、共通の資源の抽象クラスを導入する事で、
いった人的コミュニティはどこに行くのか、どういっ
r
WWW と同様にアクセス可能になった場合、こう
あるか、オーバーレイによって異なる可能性がある。
r
e
p
資源にアクセスする機構をネットワーク側から取得
6.4.4 普及への障害: 複数方式への対応
URP によって簡易に資源を指定できるようになっ
制約をかける事になる。
また、URP に操作を記述すべきかという議論があ
a
しなければ、URP によるメリットは乏しくなる。一
る。URP によって資源と探索者をランデブーさせる
u
方、将来いくら可能性があろうとも、現状でメリット
が、ランデブーした後の操作は記述できなくても良
n
が乏しいものを実装するインセンティブは低い。既
いのか。URL の場合は、GET 要求なのか POST 要求
n
存のフレームワークの URL 処理部への統合等、URP
なのか、あるいは HEAD 要求なのかは文脈で決定でき
a
を利用する環境を発展的に成長させるための現実的
たが、その前提を URP に対して仮定して良いのか。
3
l
ても、その資源が簡便に利用できるだけの機構が存在
できる事になる。但し、この方法は資源のあり方に
な壁を壊していく手段を考える必要がある。
例えば、accessor として chord.join://... 等と
2
0
0
書ける事によるメリットがあるかもしれない。
6.4.5 議論: URP 利用者の情報
condition や preference はあくまで利用者個々
効果の検証が第一の課題である。そのためには、
実際に URP を応用するシステムを作る事が望まし
E
かし、筆者は敢えて URP にこういった情報を入れる
い。具体的には、6.3.5 項で述べた応用例のシステム
J
べきであると考える。なぜならばオーバーレイはあ
試作を目指す。
らゆる意味で不均一である可能性が高いからである。
例えば、同一のオーバーレイのプロトコルにおい
等、利用環境を定める作業が必要である。URL を扱
て、匿名が「望まれる」場合と、実名が「望まれる」
うルーチンに取り入れるにはどうすべきか等も検討
場合がある。実際に匿名で参加するか実名で参加す
する予定である。
E
R
また、並行して、URP の取り扱いに関する API
P
C
URP に含めるべきでは無いとする考え方もある。し
O
T
の事情であり、資源へのポインタの伝達手段である
6.4.7 今後の課題
I
W
D
るかは利用者が決めて良い事である一方、URP を伝
える側がオーバーレイ側の希望を伝える経路があっ
ても良い筈だ。これは匿名性に限らず、資源提供の
緩いポリシーの記述にも役立つ。
一方、利用者側のクライアントプログラムには、
6.5 結論
本章では、目的別に生じたオーバーレイの自然な
発展としての統合において、URP が必要となる理
由について述べた。その上で、URP に必要かもしれ
preference および condition を評価し、場合によっ
ないいくつかの機能を列挙し、求められる条件を満
ては URP による資源探索をブロックしたり、これら
たすためにどの機能が必須であり、どの機能がオプ
のフィールドをユーザの要求に合うように書き変え
ショナルかを考察した。
たりする機構が必要になるだろう。これはブラウザ
における P3P[45] のようなものになるかもしれない。
当然、本章で述べた URP は、現状存在するオー
バーレイに対する限定された考察に基づく以上、将来
発生する全てのネットワークをカバーしているとい
6.4.6 議論: 抽象ノードの抽象と操作
オーバーレイにおける抽象ノードの抽象(クラス
化)およびその抽象に対する操作(メソッド)につ
392
う保証は無い。一方で、Universal でないが Uniform
であるポインタおよびその記述方法がオーバーレイ
統合に寄与する事は本章で述べた。
W
I
D
E
P
R
O
J
E
C
T
本章で述べたような、実際に取り扱う様々な性質
の資源を様々なオーバーレイの形で抽象化する、と
いうアーキテクチャは未だに十分成立しているとは
言えない。今後の研究課題として、オーバーレイを
より積極的に活用したアーキテクチャを実際に作成
し、
「統合分散環境」としての評価を行っていく必要
がある。
●第 部
Integrated Distributed Environment with Overlay Network
393
24
24
w
ダウンロード

PDF File - WIDE Project Homepage