- Computational view
- Panorama
The explosive growth of the Internet gives rise to the possibility
of designing large overlay networks and virtual
organizations consisting of Internet-connected computers units,
able to provide a rich functionality of services that makes use of
aggregated computational power, storage, information resources,
etc.
We would like to start our statement with the
standard definition of Computer System and then scale up to
the our definition of Overlay Computer (we emphasize some
text using underline). A plætora of overlay computer's
definitions can be found in FP6 project and presentations (see e.g. Aeolus, Mobius, Sensoria).
Definition 1 (Computer System)
A computer system is composed by a computer hardware and a
computer software.
A Computer Hardware is the physical part of a computer,
including the digital circuitry, as distinguished from the
computer software that runs within the hardware. The
hardware of a computer is infrequently changed, in
comparison with software and data.
A Computer Software is composed by three parts, namely,
system software, program software, and application software.
The System Software helps run the computer hardware and
computer system. Examples are operating systems
(OS), device drivers, diagnostic tools, servers, windowing
systems...
The Program Software usually provides tools to assist a
programmer in writing computer programs and software using
different programming languages. Examples are text editors,
compilers, interpreters, linkers,
debuggers for general purpose languages...
The Application Software allows end users to accomplish
one or more specific (non computer related) tasks industrial
automation, business software, educational software, medical
software, databases, computer games...
Starting from the previous basic skeleton definition, we elaborate
the LogNet's vision of what an Overlay Computer System is.
The reader can focus on the tiny but crucial differences between the
above and below definitions.
Definition 2 (Overlay Computer System)
An overlay computer system is composed by an overlay computer
hardware and an overlay computer software.
An Overlay Computer Hardware is the physical part of an
overlay computer, including the digital circuitry, as
distinguished from the overlay computer software that executes
within the hardware. The hardware of an overlay computer
changes frequently and it is distributed
in space and in time. Hardware is organized in a network of
collaborative computing agents connected via IP or ad-hoc
networks; hardware must be negotiated before being
used.
An Overlay Computer Software is composed by three parts,
namely, overlay system software, overlay program software, and
overlay application software.
The Overlay System Software helps run the overlay computer
hardware and overlay computer system. Examples are
network middleware playing as a
distributed opera- ting system (dOS),
resource discovery protocols, virtual intermittent protocols,
security protocols, reputation protocols...
The Overlay Program Software usually provides tools to
assist a programmer in writing overlay computer programs and
software using different overlay programming
languages. Examples are compilers,
interpreters, linkers, debuggers for
workflow-, coordination-, and
query-languages.
The Overlay Application Software allows end users to
accomplish one or more specific (non-computer related) tasks
industrial automation, business software, educational
software, medical software, databases, and computer
games...Those classes of applications deal with
computational power (Grid), file and storage retrieval
(P2P), web services (Web2.0), band-services (VoIP),
computation migrations...
Therefore, LogNet's general objectives can be resumed as follows:
to provide adequate notions and definitions of an
generic overlay computer: logic, communications, implementations,
applications, hardware;
on the basis of the above definitions, to propose a precise
architecture of an overlay computer with related execution model
and implement it;
on the basis of the above definitions, to implement useful
applications suitable to help the logical and software assembling
of an overlay computer and experiment it at large scale;
putting our savoir faire in logics, type theory, formal
systems, object-oriented, functional programming to the service of
telecommunications and the, so called Internet of the future
and of things.
- General definitions
An overlay network is a logical network which is built on top of
another physical network. Overlay networks can be constructed in
order to permit routing messages to destinations not specified by an
IP address. In what follows, we briefly describe the main entities
underneath our vision of an overlay network and an overlay computer.
Agents.
An agent in the overlay is the basic computational entity of the
overlay: it is typically a device, like a PDA, a laptop, a PC, or
smaller devices, connected through IP or other ad hoc
communication protocols in different fashions (wired, wireless).
Agents in the overlay can be thought of as being connected by
virtual or logical links, each of which corresponds to a path,
through many physical links, in the underlying network. For example,
many peer-to-peer networks are overlay networks because they run on
top of the Internet.
Colonies and colony's leaders.
Agents in the overlay are regrouped in Colonies. A colony is
a simple virtual organization composed by exactly one leader,
offering some broker-like services, and some set of agents.
The leader, being also an agent, can be an agent of a colony
different of the one it manages. Thus, agents are simple computers
(think it as an amoeba), or sub-colonies (think it as a
protozoa). Every colony has exactly one leader and at
least one agent (the leader itself). Logically an agent can be seen
as a collapsed colony, or a leader managing
itself. The leader is the only one who knows all agents of its
colony. One of the tasks of the leader is to manage
(un)subscriptions to its colony.
Resource discovery.
By adhering a colony, an agent can expose resources it has and/or
ask for resources it needs. Another task of a leader is to manage
the resources available in its colony. Thus, when an agent of the
overlay needs a specific resource, it makes a request to its leader.
A leader is devoted to contacting and negotiating with potential
servers, to authenticating clients and servers, and to route
requests. The rationale ensuring scalability is that every request
is handled first inside its colony, and then forwarded through the
proper super-leader (thus applying an
endogenous-first-exogenous-last strategy).
Orchestration.
When an agent receives an acknowledgment of a service request from
the direct leader, then the agent is served directly by the
server(s) agents, i.e. without a further mediation of the leader, in
a pure P2P fashion. Thus, the “main” program will be run on the
agent computer machine that launched the service request and
received the resources availability: it will orchestrate and
coordinate data and program resources executed on others agent
computers.
- Virtual organization
A virtual organization is a flat or hierarchical collection of
agents. An agent in the overlay is the basic computational
entity of the overlay: it is typically a device, like a PDA, a
laptop, a PC, or smaller devices, connected through IP or other
ad hoc communication protocols in different fashions (wired,
wireless). Agents in the overlay can be thought of as being
connected by virtual or logical links, each of which corresponds to
a path, through many physical links, in the underlying network. For
example, many peer-to-peer networks are overlay networks because
they run on top of the Internet. Agents may collaborate through flat
connections between colonies or hierarchical connection in
tree-based colonies. In this latter case a colony is a simple
virtual organization composed by exactly one leader, offering
some broker-like services, and some set of agents. The
leader, being also an agent, can be an agent of a colony different
of the one it manages. Thus, agents are simple computers (think it
as an amoeba), or sub-colonies (think it as a
protozoa). Every colony has exactly one leader and at
least one agent (the leader itself). Logically an agent can be seen
as a collapsed colony, or a leader managing
itself. The leader is the only one who knows all agents of its
colony. One of the tasks of the leader is to manage
(un)subscriptions to its colony.
- Execution model
We plan to investigate the theoretical study and the actual
implementation of new primitives to better interface programming
languages with overlay networks.
- Protocol view
- Panorama
As suggested by our previous definitions, we are mainly concerned by
three topics: network organization, resource discovery and
orchestration. These topics are studied in an overlay called
Arigatoni (work started by Luigi Liquori and Michel
Cosnard). Indeed Arigatoni is build around a notion of virtual
organization (colonies of agents). Following our main three topics,
network organization, resource discovery and orchestration,
Arigatoni goes deeper in the network organization and the resource
discovery (VIP and RDP). We will make an implementation of the
VIP and RDP protocols.
- Arigatoni overlay network
The Arigatoni overlay network computer
developed since 2006 in the Mascotte Project Team by
Luigi Liquori and Michel Cosnard, and then in the LogNet team, is a
structured multi-layer overlay network which provides resource
discovery with variable guarantees in a virtual organization where
peers can appear, disappear, and self-organize themselves
dynamically. Arigatoni is universal in the sense of Turing
machines, or generic as the von Neumann computer architecture
is.
Every agent asks the broker to log in the colony by declaring the
resources that it provides (with variable guarantees). Once logged
in, an agent can ask the broker for other resources. Colonies can
recursively be considered as evolved agents who can log in an
outermost colony governed by another super-leader. Communications
and routing intra-colonies go through a broker-2-broker PKI-based
negotiation. Every broker routes intra- and inter- service
requests by filtering its resource routing table, and then
forwarding the request first inside its colony, and second outside,
via the proper super-leader (thus applying an
endogenous-first-estrogen-last strategy).
Theoretically, queries are formulæ in first-order logic. When the
client agent receives notification of all (or part of) the requested
resources, then the real resource exchange is performed directly by
the server(s) agents, without any further mediation of the broker,
in a pure peer-to-peer fashion. The proposed overlay promotes an
intermittent participation in the colony. Therefore, the
routing process may lead to failures, because some agents
have quit, or are temporarily unavailable, or they were logged out
by the broker due to their poor performance or greediness.
Arigatoni features essentially two protocols: the resource
discovery protocol dealing with the process of an agent broker to
find and negotiate resources to serve an agent request in its own
colony, and the virtual intermittent protocol dealing with
(un)registrations of agents to colonies.
Dealing essentially with resource discovery and peers' intermittence
has one important advantage: the complete generality and
independence of any offered and requested resource. Arigatoni can
fit with various scenarios in the global computing arena, from
classical P2P applications (file- or bandwidth-sharing), to new
Web2.0 applications, to new V2V and V2I over MANET applications, to more sophisticated Grid and Cloud applications,
until possible, futuristic migration computations, i.e. transfer of a non-completed local run to another agent, the latter
being useful in case of catastrophic scenarios, like fire, terrorist
attack, earthquake, etc.
Arigatoni units
In what follows, we briefly introduce the logic peers underneath a
generic overlay network.
Peers' participation in Arigatoni's colonies is managed by the
Virtual Intermittent Protocol (VIP); the protocol deals with
the dynamic topology of the overlay, by allowing agent
computers to login/logout to/from a colony (using the SREG message). Due to this high node churn, the routing process may lead
to failures, because some agents have logged out, or because
they are temporarily unavailable, or because they have logged out
manu militari by the broker for their poor performance or
greediness.
The total decoupling between peers in space (peers do not
know other peers' locations), time (peers do not participate
in the interaction at the same time), synchronization (peers
can issue service requests and do something else, or may be doing
something else when being asked for services), and
encapsulation (peers do not know each other) are key features
of Arigatoni's scalability.
Agent computer (AC).
This unit can be, e.g., a cheap computer device composed by a small
RAM-ROM-HD memory capacity, a modest CPU, a  40
keystrokes keyboard (or touchscreen), a tiny screen ( 4 inch),
an IP or ad hoc connection (via DHCP, BLUETOOTH, WIFI,
WIMAX...), a USB port, and very few programs installed inside,
e.g. one simple editor, one or two compilers, a mail
client, a mini browser... Our favorite device actually is the
Internet tablet Nokia N810. Of course an AC can be a
supercomputer, or an high performance PC-cluster, a large database
server, an high performance visualizer (e.g. connected to a virtual
reality center), or any particular resource provider, even a
smart-dust. The operating system (if any) installed in the
AC is not important. The computer should be able to work in
local mode for all the tasks that it could do locally, or in
global mode, by first registering itself to one or many
colonies of the overlay, and then by asking and serving global
requests via the colony leaders. In a nutshell, the tasks of an
AC are:
Discover the address of one or many agent brokers (ABs),
playing as colony leaders, upon its arrival of itself in a
“connected area”; this can be done using the underlay network
and related technologies;
Register on one or many ABs, so entering de facto the
Arigatoni's virtual organization;
Ask and offer some services to others ACs, via the leaders
ABs;
Connect directly with other ACs in a P2P fashion, and
offer/receive some services. Note that an AC can also be a
resource provider. This symmetry is one of the key features of
Arigatoni. For security reasons, we assume that all AC come
with their proper PKI certificate.
Agent Broker (AB). This unit can be, e.g., a computer
device made by a high speed CPU, an IP or ad hoc connection
(via DHCP, BLUETOOTH, WIFI, WIMAX...), a high speed hard-disk
with a resource routing table to route queries, and an
efficient program to match and filter the routing table. The
computer should be able to work in global mode, by first
registering itself in the overlay and then receiving, filtering and
dispatching global requests through the network. The tasks of an
AB are:
Discover the address of another super-AB, representing
the super-leader of the super-colony, where the AB colony is embedded. We assume that every AB comes with its
proper PKI certificate. The policy to accept or refuse the
registration of an AC with a different PKI is left open to the
level of security requested by the colony;
Register/unregister the proper colony on the leader
AB which manages the super-colony;
Register/unregister clients and servants AC in its colony,
and update the internal resource routing table, accordingly;
Receive the request of service of the client AC;
Discover the resources that satisfy an AC request in its
local base (local colony), according to its resource routing
table;
Delegate the request to an AB leader of the direct
super-colony in case the resource cannot be satisfied in its
proper colony; it must register itself (and by product its colony)
to another super-colony;
Perform a combination of the above last two actions;
Deal with all PKI intra- and inter-colony policies;
Notify, after a fixed timeout period, or when all ACs
failed to satisfy the delegated request, to the AC client the
denial of service requested by the AC client;
Send all the information necessary to make the AC client
able to communicate with the AC servants. This notification is
encoded using the resource discovery protocol. (Finally, the AC client will directly talk with the ACs servants).
Agent Router (AR).
This unit implements all the low-level overlay network routines,
those which really have access to the IP or to the ad-hoc
connections. In a nutshell, an AR is a shared library dynamically
linked with an AC or an AB. The AR is devoted to the following
tasks:
Upon the initial start-up of an AC (resp. AB) it helps to
register the unit with one or many AB that it knows or discovers;
Checks the well-formedness and forwards packets of the two
Arigatoni's protocols across the overlay toward their destinations.
The total decoupling between peers in space (peers do not
know other peers' locations), time (peers do not participate
in the interaction at the same time), synchronization (peers
can issue service requests and do something else, or may be doing
something else when being asked for services), and
encapsulation (peers do not know each other) are key features
of Arigatoni's scalability.
Virtual organizations in Arigatoni
Agent computers communicate by first registering to the colony and
then by asking and offering services. The leader agent broker
analyzes service requests/responses, coming from its own colony or
arriving from a surrounding colony, and routes requests/responses to
other agents. Agent computers get in touch with each other without
any further intervention from the system, in a P2P fashion.
Peers' coordination is achieved by a simple program written in an
orchestration/business language à la BPEL [35], or
JOpera [35].
Symmetrically, the leader of a colony can arbitrarily unregister an
agent from its colony, e.g., because of its bad performance when
dealing with some requests or because of its high number of
“embarrassing” requests for the colony. This strategy,
reminiscent of the Roman do ut des, is nowadays called, in
Game Theory, Rapoport's tit-for-tat strategy
[39] of cooperation based on reciprocity.
Tit-for-tat is commonly used in economics, social sciences, and it
has been implemented by a computer program as a winning strategy in
a chess-play challenge against humans (see also the well known
prisoner dilemma). In computer science, the tit-for-tat
strategy is the stability (i.e. balanced uploads and downloads)
policy of the Bittorrent P2P protocol [27]
Once an agent computer has issued a request for some service, the
system finds some agent computers (or, recursively, some
sub-colonies) that can offer the resources needed, and communicates
their identities to the (client) agent computer as soon as they are
found.
The model also offers some mechanisms to dynamically adapt to
dynamic topology changes of the overlay network, by allowing
an agent (computer or broker, representing a sub-colony) to
login/logout in/from a colony. This essentially means that the
process of routing request/responses may lead to failure, because
some agents logged out or because they are temporarily unavailable
(recall that agents are not slaves). This may also lead to
temporary denials of service or, more drastically, to the complete
logout of an agent from a given colony in the case where the former
does not provide enough services to the latter.
Resource discovery protocol (RDP)
Kind of discovery.
The are mostly two mechanisms of resource discovery, namely:
The process of an AB to find and negotiate resources to serve
an AC request in its own colony;
The process of an AC (resp. AB) to discover an AB, upon
physical/logical insertion in a colony.
The first discovery is processed by Arigatoni's resource discovery
protocol, while the second is processed out of the Arigatoni overlay, using well-known network protocols, like DHCP, DNS, the
service discovery protocol SLP of BLUETOOTH, or Active/Passive
Scanning in WIFI.
The current RDP protocol version allows the request for
multiple services and service conjunctions. Adding
service conjunctions allows an AC to offer several services at the
same time. Multiple services requests can be also asked to an AB;
each service is processed sequentially and independently of others.
As an example of multiple instances, an AC may ask for three CPUs,
or one chunk of 10GB of HD, or one gcc
compiler. As an example of a service conjunction, an AC may ask for
another AC offering at the same time one CPUs, and
one chunk of 1GB of RAM, and one chunk of 10GB of
HD, and one gcc compiler. If a request succeeds,
then, using a simple orchestration language, the AC client will use
all resources offered by the servers ACs.
The RDP protocol proceeds as follows: suppose an AC  registers
– using the intermittent protocol VIP presented below – to an AB and declares its availability to offer a service  , while another
AC  , already registered, issues a request for a service  .
Then, the AB looks in its routing table and filters
against . If there exists a solution to this filter
equation, then can provide a resource to .
For example, the resource
![Im7 ${\#120242 {~\mover =\#9653 ~}[\#120226 \#120239 \#120244 =\#120232 \#120263 \#120269 \#120254 \#120261 ,\#120243 \#120258 \#120262 \#120254 \#8804 10\#120268 \#120254 \#120252 ]}$](23.png) filters against
![Im8 ${{\#120242 }^'{~\mover =\#9653 ~}{[\#120226 \#120239 \#120244 =\#120232 \#120263 \#120269 \#120254 \#120261 ,\#120243 \#120258 \#120262 \#120254 \#8805 5\#120268 \#120254 \#120252 ]}}$](24.png) , with attribute
values  and  between 5 and
10 seconds.
Routing tables in RDP.
In Arigatoni, each AB maintains a routing table 
locating the services that are registered in its colony. The
table is updated according to the dynamic registration and
unregistration of ACs in the overlay; thus, each AB maintains a
partition of the data space. When an AC asks for a resource (service
request), then the query is filtered against the routing tables
of the ABs where the query is arrived and the AC is registered; in
case of a filter-failure, the ABs forward the query to their
direct super-ABs. Any answer of the query must follow the reverse
path.
Thus, resource lookup overhead reduces when a query is satisfied in
the current colony. Most structured overlays guarantee lookup
operations that are logarithmic in the number of nodes. To improve
routing performance, caching and replication of data and search paths
can be adopted. Replication also improves load balancing, fault
tolerance, and the durability of data items.
Virtual Intermittent Protocol (VIP)
There are essentially two ways AC can register to an AB (sensible
to its physical position in the network topology), the latter being
not enforced by the Arigatoni model (see [6]):
Registration of an AC to an AB belonging to the same
current administrative domain;
Registration via tunneling of an AC to another AB belonging to a different administrative domain.
If both registrations apply, the AC is de facto working in local
mode in the current administrative domain and working in
global mode in another administrative domain. Symmetrically,
an AC can unregister according to the following simple rules
“d'étiquette”:
Unregistration of an AC is allowed only when there are no
pending services demanded or requested to the leader AB of the
colony: agent computers must always wait for an answer of the AB or for a direct connection of the AC requesting or offering the
promised service, or wait for an internal timeout (the time-frame
must be negotiated with the AB);
(As a corollary of the above) an AB cannot unregister from its
own colony, i.e. it cannot discharge itself. However, for fault
tolerance purposes, an AB can be faulty. In that case, the ACs
unregister one after the other and the colony disappear;
Once an AC has been disconnected from a colony belonging to
any administrative domain, it can physically migrate in another
colony belonging to any other administrative domain;
Selfish agents in P2P networks, called “free riders”, that
only utilize other peers' resources without providing any
contribution in return, can be fired by a leader; if the leader of a
colony finds that the agent's ratio of fairness is too small ( for a given ), it can arbitrarily decide to fire
that agent without notice. Here, the VIP protocol also checks
that the agent has no pending services to offer, or that the timeout
of some promised services has expired, the latter case means that
the free rider promised some services but finally did not provide
any service at all (not trustfulness).
Registration policies in VIP.
VIP registration policies are usually not specified in the protocol
itself; thus every agent broker is free to choose its acceptance
policy. This induces different self-organization policies and allow to
reason on colony's load-balancing and kind of colonies. Possible
politics and are:
(mono-thematic) An agent broker accept an agent in its
colony if the latter offer resources that the colony already
have in quantity  , for a given ;
(multi-thematic) An agent broker accept an agent if the
latter offer resources that the colony have in quantity , for a given ;
(unbalanced) An agent broker accept an agent always;
(pay-per-service) An agent broker accept only agents
that accept to pay some services;
(metropolis/village) An agent broker accept an agent in its
colony only if the number of citizens is greater/lesser than N;
(village) An agent broker accept an agent in its colony
only if the number of citizens is lesser than N;
(custom) An agent broker accept an agent following a
flexible meta-politics that can mix of the above politics.
iNeu: language-based primitives for network computing
Once resources (hardware, software...) have been discovered, the
agent computer that made the request may wish to use and manipulate
them; to do this, the agent computer has written a (distributed)
program using suitable Java library/dialect (the final choice
still left open by authors)
let's call it Ivonne, in honor to the great scientist John von
Neumann. Those languages are often called (terminology often
overlaps), coordination- workflow- dataflow- orchestration-
composition- metaprogramming- languages. Ivonne will have
ad hoc primitives to express sequences, iterators, cycles, parallel
split, joins, synchronization, exclusive/multi/deferred choice,
simple/multi/synchronizing merge, discriminators, pipelining,
cancellation, implicit termination, exception handling... [43].
The “main” of an Ivonne program will be runned on the agent
computer machine that launched the service request and received the
resources availability: it will orchestrate and coordinate data and
program resources executed on others agent computers.
In case of failure of a remote service – due to a network
problem or simply because of the unreliability or untrustability of
the agent that promised the resource – an exception handling
mechanism will send a resource discovery query on the fly to
recover a faulty peer and the actual state of the run represented,
in semantic jargon, by the current continuation.
We also envisage to design a run-time distributed virtual
machine, built on the top of a virtual or hardware machine, in order
to scale-up from local to distributed computations and to fit with
the distributed nature of an overlay network computer.
Communication between agent computers will performed through a
logic bus, using Web technologies, like SOAP or AJAX protocols, or a combination of Java-based JNI+RMI-protocols, or
.NET, XPCOM, D-BUS, OLE bus protocols, or
even by enriching the Arigatoni protocol suite with an ad hoc control-flow and data-flow protocol, and permitting to use it
directly inside Ivonne.
We envisage the design of an intermediate low-level distributed
assembler language where the Ivonne dialect or library could be
compiled. The intermediate machine code will recast the assembler
pseudo code
move R0 R1
à la Backus [25] in
move dataR0 from ipR0:portR0 to ipR1:portR1
where of course latency is an non-trivial issue, or
the assembler pseudo code
op R0 R1 R2
in
op on ipR0 with
ipR0:portR0:dataR0 and
ipR1:portR1:dataR1 and stockin
ipR2:portR2:dataR2
Summarizing, an overlay program will be a smooth combination
of an overlay network connectivity dealing with virtual
organizations and discovery protocols, a computation of an algorithm
resulting of the summa of all algorithms running on different
computer agents, and the coordination of all computer agents.
- Babelchord, a DHT's tower
A significant part of today's Internet traffic is generated by
peer-to-peer (P2P) applications, used originally for file sharing,
and more recently for real-time multimedia communications and live
media streaming.
Distributed Hash Tables (DHTs) or “structured overlay networks”
have gained momentum in the last few years as the breaking
technology to implement scalable, robust and efficient Internet
applications. DHTs provide a lookup service similar to a hash
table: (key, value) pairs are stored in the DHT, and any
participating node can efficiently retrieve the value associated
with a given key. Responsibility for maintaining the mapping from
names to values is distributed among the nodes, in such a way that a
change in the set of participants causes a minimal amount of
disruption. This allows DHTs to scale to extremely large numbers
of nodes and to handle continual node arrivals, departures, and
failures.
Chord [41] is one of the simplest protocols addressing
key lookup in a distributed hash table: the only operation that
Chord supports is that given a key, it routes onto a node which is
supposed to host the entry (key,value). Chord adapts efficiently as
nodes join and leave the system. Theoretical analysis and
simulations showed that the Chord protocol scales up logarithmically
with the number of nodes. In Chord, every node can join and leave
the system without any peer negotiation, even though this feature
can be implemented at the application layer. Chord uses consistent
hashing in order to map keys and nodes' addresses, hosting the
distributed table, to the same logical address space. All the peers
share a common hash function, representing the only way to map
physical addresses and keys to a single logical address space. Peers
can join the Chord just by sending a message to any node belonging
to the Chord overlay. No reputation mechanism is required to accept,
reject, or reward peers that are more reliable or more virtuous than
others. Merging two Chord rings together is a costly operation
because of the induced message complexity and the substantial time
the finger tables needs to stabilize. Separated rings having
different hash function for security reasons but wishing to access
resources (read only access) of other rings without merging could
take advantage of BabelChord.
We propose to connect smaller Chord networks in an unstructured way
via special nodes playing the role of neural synapses.
Features
Schematically, the main BabelChord's features are:
Routing over SW/HW-Barriers. Namely, the ability to
route queries through different, unrelated, DHTs (possibly
separated by firewalls) by “crossing floors”. A peer “on the
border” of a firewall can bridge two overlays (having two different
hash functions) that were not meant to communicate with each other
unless one wants to merge one floor into the other (operation with a
complexity linear in the number of nodes). The possibility to
implement strong or weak security requirements makes BabelChord suitable to be employed in Internet applications where software or
social barriers are an important issue to deal with.
Social-based. Every peer has data structures
recording peers and floors which are more “attractive” than
others. A “hot” node is a node which is stable (alive) and which
is responsible for managing a large number of (keys-values) in all
hosted DHTs. A “hot” floor is a floor responsible of a high
number of successful lookups. Following a personal “good deal”
strategy, a peer can decide to invite an hot node on a given floor
it belongs to, or to join a hot floor, or even create from scratch
a new floor (and then invite some hot nodes), or accept/decline an
invitation to join a hot floor. This social-behavior makes the
BabelChord network topology to change dynamically. As observed in
other P2P protocols, like Bittorrent, peers with similar
characteristics are more willing to group together on a private
floor and thus will eventually improve their overall communications
quality. Finally, the “good deal” strategy is geared up to be
further enhanced with a reputation-system for nodes and floors.
Neural-inspired. Since every floor has a proper hash
function, a BabelChord network can be thought as a sort of
meta overlay network or meta-DHT, where inter floors
connections take place via crossroad nodes, a sort of neural
synapses, without sharing a global knowledge of the hash functions
and without a time consuming floor merging. The more synapses you
have the higher the possibility of having successful routing is.
Suitable applications
Because of the above original features, the following are examples
of applications for which BabelChord can provide a good groundwork
(in addition, of course, to all genuine Chord-based applications,
like cooperative mirroring, time-shared storage, distributed indexes
and large-scale combinatorial search).
Anti Internet censorship applications. Internet
censorship is the control or the suppression of the publishing or
accessing of information on the Internet. Many applications and
networks have been recently developed in order to bypass the
censorship: among the many we recall Psiphon
( http://psiphon.ca), Tor ( http://www.torproject.org),
and many others. BabelChord can support such applications by taking
advantage of intra-floor routing in order to bypass software
barriers.
Fully Distributed social-networks applications.
Social-networks are emerging as one of the Web 2.0
applications. Famous social networks, such as Facebook or LinkedIn
are based on a client-server architecture; very often those sites
are down for maintenance. BabelChord could represent a scalable and
reliable alternative to decentralize key search and data storage.
Large-scale brain model and simulations. (Via a
distributed, neural-based, network.) As well explained by
R.D. DeGroot (Project founded by KNAW, Netherlands), supercomputers
exist now with raw computational powers exceeding that of a human
brain. Technological and production advances will soon place such
computing power within the hands of cognitive and medical
neuroscience research groups. For the first time it will be
possible to execute brain-scale simulations of cognitive and
pharmacological processes over millions and then billions of neurons
- even at the biological model level. BabelChord could help modeling
as a meta- overlay network the human brain. A paper has been
written and submitted to an international workshop [21].
- Synapse, interconnecting heterogeneous overlay networks
We investigate Synapse [23], a scalable protocol for
information retrieval over the inter-connection of heterogeneous
overlay networks. Applications of top of Synapse see those
intra-overlay networks as a unique inter-overlay network.
Scalability in Synapse is achieved via co-located nodes, i.e. nodes
that are part of multiple overlay networks at the same time.
Co-located nodes, playing the role of neural synapses and
connected to several overlay networks, give a larger search area
and provide alternative routing.
Synapse can either work with “open” overlays adapting their
protocol to synapse interconnection requirements, or with “closed”
overlays that will not accept any change to their protocol.
Built-in primitives to deal with social networking
give an incentive for nodes cooperation.
Results from simulation and experiments show that Synapse is
scalable, with a communication and state overhead scaling similarly
as the networks interconnected. thanks to alternate routing paths,
Synapse also gives a practical solution to network partitions.
We precisely capture the behavior of traditional metrics of overlay
networks within Synapse and present results from simulations as well
as some actual experiments of a client prototype on the Grid'5000
platform. The prototype developed implements the Synapse protocol in
the particular case of the inter-connection of many Chord overlay
networks.
The inter-connection of overlay networks has been recently
identified as a promising model to cope with today's Internet issues
such as scalability, resource discovery, failure recovery or routing
efficiency, in particular in the context of information retrieval.
Some recent researches have focused on the design of mechanisms for
building bridges between heterogeneous overlay networks for the
purpose of improving cooperation between networks that have
different routing mechanisms, logical topologies and maintenance
policies. However, more comprehensive approaches of such
inter-connections for information retrieval and both quantitative
and experimental studies of its key metrics, such as satisfaction
rate or routing length, are still missing.
Many disparate overlay networks may not only simultaneously co-exist
in the Internet but also compete for the same resources on shared
nodes and underlying network links. One of the problems of the
overlay networking area is how heterogeneous overlay networks may
interact and cooperate with each other. Overlay
networks are heterogeneous and basically unable to cooperate each
other in an effortless way, without merging, an operation which is
very costly since it not scalable and not suitable in many cases for
security reasons. However, in many situations, distinct overlay
networks could take advantage of cooperating for many purposes:
collective performance enhancement, larger shared information,
better resistance to loss of connectivity (network partitions),
improved routing performance in terms of delay, throughput and
packets loss, by, for instance, cooperative forwarding of flows.
As a basic example, let us consider two distant databases. One node
of the first database stores one (key, value) pair which is
searched by a node of the second one. Without network cooperation
those two nodes will never communicate together. As another example,
we have an overlay network where a number of nodes got isolated by
an overlay network failure, leading to a partition: if some or all
of those nodes can be reached via an alternative overlay network,
than the partition “could” be recovered via an alternative
routing.
In the context of large scale information retrieval, several
overlays may want to offer an aggregation of their information/data
to their potential common users without losing control of it.
Imagine two companies wishing to share or aggregate information
contained in their distributed databases, obviously while keeping
their proprietary routing and their exclusive right to update it.
Finally, in terms of fault-tolerance, cooperation can increase the
availability of the system, if one overlay becomes unavailable the
global network will only undergo partial failure as other distinct
resources will be usable.
We consider the tradeoff of having one vs. many overlays as a
conflict without a cause: having a single global overlay has many
obvious advantages and is the de facto most natural
solution, but it appears unrealistic in the actual setting. In some
optimistic case, different overlays are suitable for collaboration
by opening their proprietary protocols in order to build an open
standard; in many other pessimistic cases, this opening is simply
unrealistic for many different reasons (backward compatibility,
security, commercial, practical, etc.). As such, studying protocols
to interconnect collaborative (or competitive) overlay networks is
an interesting research vein.
The main contribution of thisresearch vein is to introduce, simulate
and experiment with Synapse, a scalable protocol for
information retrieval over the inter-connection of heterogeneous
overlay networks. The protocol is based on co-located nodes, also
called synapses, serving as low-cost natural candidates for
inter-overlay bridges. In the simplest case (where overlays to be
interconnected are ready to adapt their protocols to the
requirements of interconnection), every message received by a
co-located node can be forwarded to other overlays the node belongs
to. In other words, upon receipt of a search query, in addition to
its forwarding to the next hop in the current overlay (according to
their routing policy), the node can possibly start a new search,
according to some given strategy, in some or all other overlay
networks it belongs to. This obviously implies to providing a
Time-To-Live value and detection of already processed queries, to
avoid infinite loop in the network, as in unstructured peer-to-peer
systems.
We also study interconnection policies as the explicit
possibility to rely on social based strategies to build these
bridges between distinct overlays; nodes can invite or can be
invited.
In case of concurrent overlay networks, inter-overlay routing
becomes harder, as intra-overlays are provided as some black boxes:
a control overlay-network made of co-located nodes maps one
hashed key from one overlay into the original key that, in turn,
will be hashed and routed in other overlays in which the co-located
node belongs to. This extra structure is unavoidable to route
queries along closed overlays and to prevent routing loops.
Our experiments and simulations show that a small number of
well-connected synapses is sufficient in order to achieve almost
exhaustive searches in a “synapsed” network of structured overlay
networks. We believe that Synapse can give an answer to
circumventing network partitions; the key points being that:
(i) several logical links for one node leads to as many
alternative physical routes through these overlay, and
(ii) a synapse can retrieve keys from overlays that it doesn't even know
simply by forwarding their query to another synapse that, in turn, is
better connected.
Those features are achieved in Synapse at the cost of some additional
data structures and in an orthogonal way to ordinary techniques of
caching and replication. Moreover, being a synapse can allow for the
retrieval of extra information from many other overlays even if we are
not connected with.
|
SYM A
= 0.05