Transcript Content Routing

Virtual Organizations
in the Arigatoni Overlay
Network
Michel Cosnard
Luigi Liquori
INRIA, France
INRIA, France
[email protected]
[email protected]
Raphael Chand
INRIA, France
[email protected]
Talk Outline

Context and Arigatoni Model

Arigatoni’s Intermittence Rewriting Semantics

(a bit of) Arigatoni’s Resource Discovery

Arigatoni’s Protocol Evaluation

Conclusion and what’s next
Virtual Organizations in the Arigatoni Overlay Network — L. Liquori et al.
2
Context: Global Computing


Global Computing Communication Paradigm:
computation via a seamless, geographically
distributed, open-ended network of bounded
resources owned by ”Individuals”
Examples






Internet (IP graph, a.k.a. “the backbone”, sharing)
Telephone Network (Overlay with QoS)
GRID (computing power sharing)
P2P (data sharing)
VoIP (band sharing)
Web services (“semantic infos” sharing)
Virtual Organizations in the Arigatoni Overlay Network — L. Liquori et al.
3
Context: Overlay Networks

Challenges




Virtual Organization (Colony)



How individuals organize themselves to share resources
transparently
How the organization evolves in time and in space transparently
Resource Discovery



Virtual Organizations of Individuals
Resource Discovery between Individuals
(of course … Security, Scalability, Reliability, and tutti frutti …)
How single resources, offered by individuals, are discovered
How changed states of resources are upgrated in routing tables
… The Arigaroni Overlay Network (©INRIA)
Virtual Organizations in the Arigatoni Overlay Network — L. Liquori et al.
4
Global Computers, Brokers, Routers

Global Computers (GCU)







Global Brokers (GBU)






Device of any size (GSM, PDA, Laptop, …, Cluster of PCs, …)
Discontinuous participation in the Virtual Organization (Colony)
Partial/Zero knowledge of the current Virtual Organization
Ask and provide services with variable guarantees
Can work in Local Mode or in Global Mode
Motto: Global Mode … ask to the Colony boss, and wait for the
best …if the Colony boss ask for something do your best …
Colony’s leader, but just individual in a surrounding “SuperColony”
Register/Unregister GCU in the own colony
Send/Receive GCU’s queries
Contact GCUs in its population or contact its direct SuperGBs
Trust their population at any level of the negotiation (via e.g. PKI)
Global Routers (GRU)

Send/Receive Packets via a protocol (GIP) between GCU and GBU
Virtual Organizations in the Arigatoni Overlay Network — L. Liquori et al.
5
Arigatoni Overlay Network Topology






Arigatoni, Overlay Network composed by Colonies and SubColonies
Global Brokers (GBU) = Routing queries (un/register, resource discovery)
Global Computers (GCU) = Ask/provides resources interchangeably
Global Router (GRU) = Dispatch packets around the network
Hierarchical tree structured organization
Leader
GB
Once the resource/s is/are negotiated, GCUs
communicate in P2P fashion
Leader
…
Leader
…
GB1
GC1
…
Leader
GB
…
SubColony
GCk
GC1
GBn
GC1
…
…
GCk
Individuals
GCk
SubColony
Colony
Virtual Organizations in the Arigatoni Overlay Network — L. Liquori et al.
6
Syntax: Colonies and Communities

Colony syntax

Community (Soup) syntax
Virtual Organizations in the Arigatoni Overlay Network — L. Liquori et al.
7
Syntax Examples
Virtual Organizations in the Arigatoni Overlay Network — L. Liquori et al.
8
Cardelli and Gordon Ambients …

“In the early days of the Internet one could
rely on a flat name space given by IP
addresses; knowing the IP address of a
computer would very likely allow now to talk to
that computer in some way. This is no longer
the case: firewalls partition the Internet into
administrative domains that are isolated from
each other except for rigidly controlled
pathways. System administrators enforce
policies about what can move through
firewalls and how [...]”
Virtual Organizations in the Arigatoni Overlay Network — L. Liquori et al.
9
Arigatoni: Registration Modalities

Registration of a GCU to the GBU leader of a colony
belonging to the same current administrative domain of
the GCU

Registration via remote tunneling of an GCU to another
GBU leader of a colony belonging to a different
administrative domain of the GCU

Summarizing, one GCU register to the GBU leader of the
colony belonging to the same administrative domain in
which it resides and to some other GBUs via tunneling
Virtual Organizations in the Arigatoni Overlay Network — L. Liquori et al.
10
Arigatoni: Unregistration Modalities

Unregistration of a GCU when there are no pending
services demanded or requested to the leader GBU of the
colony it belongs. The colony accepts the unregistration
only if the colony itself will not be corrupted

A GBU cannot unregister from its own colony (i.e. it cannot
discharge itself). For fault tolerance purposes, a GBU can
be faulty. In that case, the GCUs will unregister one after
the other and the colony will “disappear”

Once a GCU has been disconnected from a colony
belonging to any administrative domain, it can migrate in
another colony belonging to any other administrative
domain (“emigrant” model)
Virtual Organizations in the Arigatoni Overlay Network — L. Liquori et al.
11
Arigatoni Overlay Network@glance
Virtual Organizations in the Arigatoni Overlay Network — L. Liquori et al.
12
GCU’s Registration Unregistration

A GCU join a Colony

A GCU leave a Colony
Virtual Organizations in the Arigatoni Overlay Network — L. Liquori et al.
13
COL’s Registration Unregistration

Colony Registration

Colony Unregistration
Virtual Organizations in the Arigatoni Overlay Network — L. Liquori et al.
14
Colonies not in the Same Domain

Linking two Colonies

UnLinking two Colonies
Virtual Organizations in the Arigatoni Overlay Network — L. Liquori et al.
15
Contextual and Congruence

Morris like rules
Virtual Organizations in the Arigatoni Overlay Network — L. Liquori et al.
16
Join/Leave a Colony in a Different
Administrative Domain

Individual in IP1 knows “friends” inhabitant of the colony in
IP2. Then, via an explicit ssh the laptop can log into the
desktop and send a global request to the “mother colony”.
As such, the laptop works in its local mode while the
desktop works in global mode. No ad hoc rewriting rules
in the Arigatoni virtual organization

Individual in IP1 knows no inhabitant of the colony in IP2,
but it knows the address of the leader of the colony. Via
ssh-tunnel a virtual clone of the remote individual on
behalf of the leader of the colony is created and registered.
As such, the laptop works in local mode while the clone
works in global mode. This mechanism is reminiscent of
the Virtual Private Network technology (VPN). We need
4 Extra Rewriting Rules
Virtual Organizations in the Arigatoni Overlay Network — L. Liquori et al.
17
GCU not in the Same Domain
Virtual Organizations in the Arigatoni Overlay Network — L. Liquori et al.
18
Colonies not in the Same Domain
Virtual Organizations in the Arigatoni Overlay Network — L. Liquori et al.
19
Free Riders in Overlay Networks
In economics and political science, free riders are
actors who consume more than their fair share of
a resource, or shoulder less than a fair share of
the costs of its production …
The free rider problem is the question of how to
prevent free riding from taking place, or at least limit
its negative effects …
Because the notion of “fairness” is a subject of
controversy, free riding is usually only considered to
be an economic “problem” when it leads to the
non-production or under- production of a public good,
and thus to Pareto inefficiency, or when it leads to
the excessive use of a common property resource.
[From Wikipedia].

Virtual Organizations in the Arigatoni Overlay Network — L. Liquori et al.
20
Arigatoni Rules to “Fire” Free Ridings
Virtual Organizations in the Arigatoni Overlay Network — L. Liquori et al.
21
Glance of Resource Discovery Protocol
I2CS, Neuchatel, June 06, LENS

GC issues service request to
the system via its GB leader

The GB finds “some” GCs
able to serve the request
using an O.O. lookup

Report “some” GCs that
accepted to serve it

GC talks with the GCs in a
P2P fashion
[Type = CPU]
[Type < 20s]
[Type = CPU]
[Time < 10s]
GCB
S3
GCC
[Type = CPU]
[Mem < 10M]
Arigatoni
S’
[Type = CPU]
[Time > 5s]
Service Request

S2
S1
GCA
Simple Constraint Language
+ First-order Matching algos à
la Nancy’s Rho-calculus
Virtual Organizations in the Arigatoni Overlay Network — L. Liquori et al.
22
Glance of Resource Discovery Protocol
I2CS, Neuchatel, June 06, LNCS

S = [Type = CPU] & [Time > 10s]
A

Selective intra-colony search mode

uses less resources

can lead to poor delay
C
D
E
F
[Type = CPU]
[Time > 10]

B
G
H
Exhaustive search mode


uses more resources
can improve delay
GC3
GC2
GC1
S3
[Type = MEM]
[Capa < 20]
S2
[Type = CPU]
[Time < 200]
[Type = CPU]
[Time < 20]
S1
Exhaustive
Selective intra-colony
intra-colony search
search
Virtual Organizations in the Arigatoni Overlay Network — L. Liquori et al.
23
Experimental Evaluation

Sample Topology

GeorgiaTech-ITM (transit-stub)
Virtual Organizations in the Arigatoni Overlay Network — L. Liquori et al.
24
The Rationale of the Simulation



We start with a fully connected topology
The rationale is apply a number of rewriting
rules de/connecting GCU/GBU from the
topology and then do the experiment
We study the impact of the disconnections
using a variable   [0..100]%
Virtual Organizations in the Arigatoni Overlay Network — L. Liquori et al.
25
Average Acceptation Ratio

a
Virtual Organizations in the Arigatoni Overlay Network — L. Liquori et al.
26
Service Acceptation Ratio

b
Virtual Organizations in the Arigatoni Overlay Network — L. Liquori et al.
27
Standard Deviation of Accept Rate
Virtual Organizations in the Arigatoni Overlay Network — L. Liquori et al.
28
Real Example in a Grid Arena
Virtual Organizations in the Arigatoni Overlay Network — L. Liquori et al.
29
In Fine…


Arigatoni: Lightweight Overlay Network for dynamic
Resource Discovery. Achievements

Intermittence

Generality

Asynchronicity

Scalability
Current, future work

More functionalities (service instances, conjunctions)

Statistical model of the framework

Protoimplementation,deployment (PlanetLab,G5000)
Virtual Organizations in the Arigatoni Overlay Network — L. Liquori et al.
30
Questions?
Virtual Organizations in the Arigatoni Overlay Network — L. Liquori et al.
31
Resource Discovery Protocol


Routing tables maintained at each GB
⇒ set of services registered in each Colony
Always search in own colony first: encapsulation




Service request for service S’




Local colony of GCs
Other sub-colonies in Colony
Other Colonies via the GB leader = OO delegationbased
Search GCs in local colony that accept to serve S’
Search in other sub-colonies
If none are found, delegate to the leader GB …
Looks much like “method lookup” in OO languages…
Virtual Organizations in the Arigatoni Overlay Network — L. Liquori et al.
32
Context: Overlay Networks
Focus
Treatonmultiple
the application
hops
through IP layer
network as one
hop in an overlay network
B
A
C
Overlay Network
Physical Network
Virtual Organizations in the Arigatoni Overlay Network — L. Liquori et al.
33
Resource Discovery Protocol
Virtual Organizations in the Arigatoni Overlay Network — L. Liquori et al.
34
Resource Discovery Protocol (Sketch)

Encapsulation of resources in colonies

Always search in colony first

Delegate if no GCs are found
A
B
C
⇒ prevents super brokers
from begin overloaded
D
E
F
G
GC3
Type=CPU
Time>10
H
GC2
GC1
S3
Type=MEM
Capa < 20
S2
Type =CPU
Time<200
Virtual Organizations in the Arigatoni Overlay Network — L. Liquori et al.
S1
Type=CPU
Time < 20
35