Dienste in Ad-Hoc-Netzen
Beschreibung, Auffindung und Motivation
Dr. Birgitta König-Ries
Michael Klein
Philipp Obreiter
DIANE-Projekt: Dienste in Ad-hoc-Netzen
Universität Karlsruhe (TH)
http://www.ipd.uni-karlsruhe.de/DIANE
Februar 2004
1
Ziel
Integrierte Nutzung verteilter Ressourcen
Peer-to-Peer-Systeme
Grid Computing
Föderierte Datenbanken
Autonomic Computing
Randbedingungen?
Problembereiche?
Ansätze?
2
Ad-hoc-Netze
Randbedingungen der Ressourcennutzung
Automatisierung
Effizienzanforderungen
Autonomie
Selbstorganisation
3
Randbedingungen der Ressourcennutzung
föderierte Datenbank
Napster-artige Systeme
Automatisierung
Effizienzanforderungen
Autonomie
Automatisierung
Effizienzanforderungen
Selbstorganisation
Gnutella-artige Systeme
Selbstorganisation
Ad-hoc-Netze
Automatisierung
Effizienzanforderungen
4
Autonomie
Selbstorganisation
Autonomie
Automatisierung
Effizienzanforderungen
Autonomie
Selbstorganisation
Szenario
Gateway Service
In: Access Data
Out: Received Mails
Transformation
Service
In: Compressed
File
Out: File
Query Service
In: Course
Out: Academic
calendar
Document Service
In: -Out: article on
GROUP-BY operator
5
Wann und wo
Mehr über
sind
meine
MeineSQL?
Mails?
DBVorlesungen?
Problembereiche
Document Service
In: -Out: article on
GROUP-BY
operator
6
Mehr über
SQL?
Problembereiche
Angebote und Nachfragen
müssen:
 beschrieben werden
Document Service
In: -Out: article on
GROUP-BY
operator
7
Mehr über
SQL?
Problembereiche
Angebote und Nachfragen
müssen:
 beschrieben werden
 zu einander kommen
Document Service
In: -Out: article on
GROUP-BY
operator
8
Mehr über
SQL?
Problembereiche
Angebote und Nachfragen
müssen:
 beschrieben werden
 zu einander kommen
 abgeglichen werden
Document Service
In: -Out: article on
GROUP-BY
operator
9
?
=
Mehr über
SQL?
Problembereiche
$$$
Document Service
In: -Out: article on
GROUP-BY
operator
10
Angebote und Nachfragen
müssen:
 beschrieben werden
 zu einander kommen
 abgeglichen werden
Mehr über
SQL?
Geräte müssen zur
Ressourcenbereitstellung
motiviert werden
Vision: Dienstorientiertes Rechnen zur verteilten
Ressourcennutzung
Anwendung
veröffentlicheDienst
sucheDienst
führeDienstAus
Dienstorientierte Middleware
Übermittlung
Cross-Layer-Events
4. Transport
3. Network
2. Datalink
11
1. Physical
DIANE
Überblick
(Semantische) Dienstbeschreibung
M
O
T
I
V
A
T
I
O
N
(Dezentrale) Dienstsuche
(Effiziente) Dienstausführung
Transparente Dienstkombination
12
S
I
M
U
L
A
T
I
O
N
Dienstbeschreibung – Stand der Forschung (1)
Nachrichtenbasierte Dienstbeschreibung
incoming
messages
outgoing
messages
Service
 Beispiele: IDLs (CORBA, DCOM, EJB), WSDL, ebXML, …
Druckdienst:
PrintRequest
Message
url : String
resolution: ResType
13
input
Service
Dienstbeschreibung – Stand der Forschung (1)
Nachrichtenbasierte Dienstbeschreibung
incoming
messages
outgoing
messages
Service
 Beispiele: IDLs (CORBA, DCOM, EJB), WSDL, ebXML, …
Probleme
 Funktionalität kann nur aus dem
Nachrichtenfluss geraten werden
 keine Unterstützung der Konfiguration
Anwendungsbereich
 halbautomatische Suche
14
Dienstbeschreibung – Stand der Forschung (2)
Zustands-/Nachrichtenbasierte Dienstbeschreibung
incoming
messages
outgoing
messages
Service
state before
execution
state after
execution
 Beispiele: DAML-S/OWL-S Profile, ICL, …
PrintRequest
Message
url : String
resolution: ResType
input
:Service
:Document
LocallyAvailable
15
precondition
effect
:Document
Printed
Dienstbeschreibung – Stand der Forschung (2)
Zustands-/Nachrichtenbasierte Dienstbeschreibung
incoming
messages
outgoing
messages
Service
state before
execution
state after
execution
 Examples: DAML-S/OWL-S Profile, ICL, …
Probleme
 getrennte Beschreibung der Funktionalität in
Nachrichten und Zuständen Zusammenhang unklar
 keine Unterstützung der Konfiguration
16
Anwendungsbereich
 halbautomatische Suche
Automatische Suche: Anforderungen
 Funktionalität
 klare Bedeutung der Begriffe
 explizite Modellierung des Zusammenhangs zwischen Vorund Nachzustand
 Konfigurationsprozess
 explizite Beschreibung des Ablaufs der Dienstnutzung
17
DIANE Service Descriptions (DSD) (1)
I. obere Dienstontologie
 Task: allgemeine Struktur einer
Dienstbeschreibung
 einheitlich, klein
Service
Prec
InfoState
Effect
II. Ontologien für Dienstkategorien
 wenige
 Einschränkung der möglichen Vor- und
Nachbedingungen
 Beispiel: InformationService
InfoState
Document
Author
Title
Topic
Rel. Model
Rel. Algebra
SQL
SELECT
UPDATE
III. Domänenontologien
 Vokabular zur Beschreibung einzelner
Domänen
 viele, verteilt
 Beispiele: Datenbanken, Orte, Schuhe,…
IV. Instanziierung
 schrittweise Konfiguration
18
DSD: Beispiel (2)
INe
Resolution
Type
PrintRequest
Message
url : String
resolution: ResType
input
<black-white>
:ColorType
resolution
color
:Service
:LocallyAvailable precondition
entity
entity
:Document
<pdf>
:FormatType
dc:format
filesize
INe
Integer
19
:Printed
effect
time
location
dc:identifier
INx
String
OUTe
Time
OUTx
Location
Vorteile des Ansatzes
 Ontologiebasierung für klare Bedeutung
 vereinheitlichte, aber flexible Struktur durch Schichtung
 Funktionalität ist explizit beschrieben
 Zusammenhang zwischen Vor- und Nachzustand
 Einfluss der Parameter
 Konfigurationsprozess ist explizit beschrieben
Anwendungsbereich:
 automatische Suche
20
Michael Klein, Birgitta König-Ries: A Process and a Tool for Creating Service Descriptions based on DAML-S
4th VLDB Workshop on Technologies for E-Services (TES'03), Berlin, 2003
Michael Klein, Birgitta König-Ries, Philipp Obreiter: Stepwise Refinable Service Descriptions: Adapting DAML-S to Staged
Service Trading, 1st International Conference on Service Oriented Computing (ICSOC-03), Trento, Italien, 2003.
Überblick
(Semantische) Dienstbeschreibung
M
O
T
I
V
A
T
I
O
N
(Dezentrale) Dienstsuche
(Effiziente) Dienstausführung
Transparente Dienstkombination
21
S
I
M
U
L
A
T
I
O
N
Dienstsuche: Ansätze (1)
(Zentrales)
Dienstverzeichnis
 Proaktiv
 benötigt
Infrastruktur
JXTA Search
UDDI
Napster
22
verteilte
Hashtabellen
 beschränkte
Ähnlichkeitssuche
 nicht an
Netztopologie
angepasst
Fluten
 Reaktiv
 Ressourenintensiv
Pastry
Jini
Chord
Freenet
JXTA Search
Gnutella
CAN
dezentrale, semantische Dienstsuche
Ziel:
Dienstsuche, die
 ohne Infrastruktur funktioniert
 Ähnlichkeit berücksichtigt
 ressourcenschonend ist
 für dynamische Umgebungen
geeignet ist.
23
Grundidee:
Lege logische Struktur über das
vorhandene Netzwerk
 welche sich am Wissen orientiert,
welche Dienste angeboten werden,
 welche Such- und
Angebotsnachrichten geschickt
leitet
 welche bei Änderung des
physischen Netzes adaptiert wird
Overlay
A
2
C
3
B
A
E
1
C
D
physisches Netz
E
Dienstsuche: Lösungen
Dienstankündigung
1
5
2
3
6
any
cast 7
10
any
cast 11
4
8
12
9
Dienstsuche
findService
Cluster-Overlay
Ring-Overlay
findService
Dienstvergleich
Lanes-Overlay
routeMessage
routeMessage
4. Transport
4. Transport
3. Network
3. Network
sendPacket
sendPacket
sendPacket
2. Data Link
2. Data Link
2. Data Link
1. Physical
1. Physical
1. Physical
sendMessage
4. Transport
24
findService
Lanes: Idee
1
2
3
4
5
any
cast
6
7
8
9
any
cast
 Keine feste Zuordnung in
x-Richtung
 parallele Bahnen von
Knoten
10
 Innerhalb Bahn:
Definierte Nachbarschaft
11
12
 Von außerhalb: Alle
Knoten einer Bahn gleich
 Verwende AnycastRouting in x-Richtung
25
Michael Klein, Birgitta König-Ries, Philipp Obreiter
Lanes - A Lightweight Overlay for Service Discovery in Mobile Ad Hoc Network
3rd Workshop on Applications and Services in Wireless Networks (ASWN2003), Bern
Lanes: Service Trading
Dienstankündigung
1
2
5
any
cast
6
9
any
cast
10
3
7
11
4
8
12
Dienstsuche
26
Algorithmen der Lanes-Struktur
 Login/Logoff-Algorithmus
 Zutritt in die bzw. Austritt aus der Lane
 Dienstankündigung-Algorithmus
 Dienstbekanntgabe innerhalb der Lane
 Dienstsuche-Algorithmus
 Interne und anycast Suche
 Split-Algorithmus, Merge-Algorithmus
 Korrektur der Lanegröße
 LaneBroken-Algorithmus
 Korrektur nach unangekündigtem Austritt
27
Ping-Nachrichten: Sorgen für die Pflege der Lanes
Vorteile von Lanes
 Spezialisiert für dynamische Topologien
 Wenige Strukturbedingungen
 Topologiebewusste Algorithmen
 Selbstjustierende Parameter: Anpassung an die
aktuelle regionale Netzwerkprofil
 Vollständig dezentral, kein Fluten, kein Hashen
 Unabhängig von Dienstbeschreibung
 Aber: Spezialisiert für Dienstaushandlung
( 2 Dimensionen)
28
Überblick
(Semantische) Dienstbeschreibung
M
O
T
I
V
A
T
I
O
N
(Dezentrale) Dienstsuche
(Effiziente) Dienstausführung
Transparente Dienstkombination
29
S
I
M
U
L
A
T
I
O
N
Fallbeispiel: Kooperation in Lanes
Warum soll man
Dienste anbieten?
Dienstankündigung
1
Warum soll man sich
mit Dienstsuchen und
Dienstnutzung
zurückhalten?
30
2
5
any
cast
6
9
any
cast
10
3
7
11
4
8
12
Dienstsuche
Warum soll man Dienstsuchen weiterleiten?
Warum soll man
Dienstangebote
speichern und
weiterleiten?
Warum soll man
Dienstsuchen mit
-angeboten
vergleichen?
Anreizmuster
Frage: Welche Arten von Anreizen gibt es, für ein
anderes Gerät eine Aktion durchzuführen?
Anreizmuster
motiviert durch
Vertrauen
vertrauensbasierte
Anreizmuster
identitätsbas.
Vertrauen
Kollektivmuster
verhaltensbas.
Vertrauen
sofortige
Gegenleistung
Gemeinschaftsmuster
handelsbasierte
Anreizmuster
Tauschhandelsmuster
versprochene
Gegenleistung
wertpapierbasierte
Anreizmuster
Schuldner
Aussteller
Beliebiges Gerät
Dediziertes Gerät
ist Schuldner
Eigenwechselmuster
Banknotenmuster
Wechselmuster
Scheckmuster
ist nicht
Schuldner
31
motiviert durch
Gegenleistung
Philipp Obreiter, Jens Nimis
A Taxonomy of Incentive Patterns - The Design Space of Incentives for Cooperation
2nd Workshop on Agents and Peer-to-Peer Computing (AP2PC'03), Melbourne
Eigenschaften der Anreizmuster
Anreizmuster
Eigenschaften
Rollen
vertrauensbasiert
Kollektivmuster
32
Tauschhandelsmuster
wertpapierbasiert
(Eigenwechselmuster)
symmetrisch
asymmetrisch
Reputation
Gegenleistung
Eigenwechsel
−
+
o
asymmetrisch
Art der Belohnung
Durchsetzbarkeit
der Belohnung
Gemeinschaftsmuster
handelsbasiert
keine
Aufwand
klein
mittel
klein
groß
Skalierbarkeit
−−
−
+
o
Fallbeispiel: Anreizschema für Lanes
Warum Dienste anbieten?
um Eigenwechsel zu bekommen
(Wechselversprechen: Dienst)
Dienstankündigung
Warum sparsame
Dienstbenutzung?
um Eigenwechsel nicht
ausstellen zu müssen
(Wechselversprechen:
Dienst)
1
um Eigenwechsel nicht
ausstellen zu müssen
(Wechselversprechen:
Dienstvergleich)
33
9
Warum Dienstangebote
weiterleiten?
2
3
Warum sparsame
Dienstsuche?
5
4
any
cast
6
7
8
any
cast
10
11
12
um gute Reputation zu erhalten
Warum Dienstsuchen
speichern und mit Angeboten
vergleichen?
um Eigenwechsel zu bekommen
(Wechselversprechen:
Dienstvergleich)
Dienstsuche
Warum Dienstsuchen weiterleiten?
um gute Reputation zu erhalten
Überblick
(Semantische) Dienstbeschreibung
M
O
T
I
V
A
T
I
O
N
(Dezentrale) Dienstsuche
(Effiziente) Dienstausführung
Transparente Dienstkombination
34
S
I
M
U
L
A
T
I
O
N
Evaluation durch Simulation
runTest(plan)
Meta
S
I
M
U
L
A
T
O
R
instantiateUser(param)
Benutzer
userFunctions...
Protokoll
P1
P2
sendMessage(device)
Netzwerk
connected(device1, device2)
Verbindung
35
Michael Klein
DIANEmu - A Java Based Generic Simulation
Environment for Distributed Protocols
Download: http://www.ipd.uni-karlsruhe.de/DIANE
Benutzerschicht
Ziel: Realitätsgetreues Modell der Benutzer
mögliche Aktivitäten
Prioritäten der
Benutzer
Aktivitätsmodell
Ablauf der Aktivitäten
Bewegung zu Aktivität
Umweltmodell
36
Pfade
Orte
Dienst während Aktivität
Bewegungsmodell
Dienstmodell
Liste:
(Zeit, Koordinate)
Liste:
(Zeit, Dienstaufruf)
Tobias Breyer, Michael Klein, Philipp Obreiter, Birgitta König-Ries
Activity-Based User Modeling in Service-Oriented Ad hoc Networks
First Working Conference on Wireless On-demand Network Systems (WONS 2003), Trento
Evaluierung von Lanes
Einstellungen:
1.
2.
3.
4.
15 Geräte
Testdauer 3600s
Aktion jede 60 Sekunden
Ping Nachrichten bei Lanes jede 15 sec
Aufwand [ #Nachrichten/Suchanfrage]
35
30
25
20
Triviale Suche
15
Lanes
10
5
0
37
∞0
10
10
520
3,3
30
2,5
40
2
50
Dynamik [ Verweildauer in Min.]
Fairness: Korrelationskoeffizient und Regressionsgerade
Aus Messungen abgeleitete Werte:
1. Korrelationskoeffizient r (Findungen-Vergleiche)
2. Steigung der Regressionsgerade (b)
Einstellungen: 4400 Suchen, 15 Kooperative, 5 Unkooperative
Lanes
r=-0,18
Kooperative
160
140
120
100
80
60
40
20
0
0
200
r=0,69
Unkooperative
Individualnutzen [Findungen]
Individualnutzen [Findungen]
Kooperative
38
SLanes
400
600
Individualaufwand [Vergleiche]
800
#Findungen
b=0,54 #Vergleiche
Unkooperative
180
160
140
120
100
80
60
40
20
0
0
100
200
300
400
Individualaufwand [Vergleiche]
500
Zusammenfassung
(Semantische) Dienstbeschreibung
M
O
T
I
V
A
T
I
O
N
(Dezentrale) Dienstsuche
(Effiziente) Dienstausführung
Transparente Dienstkombination
39
S
I
M
U
L
A
T
I
O
N
Anforderungen und Lösungsansätze
Ad-hoc-Netze
Angebote und Nachfragen
müssen:
Automatisierung
Effizienzanforderungen
Autonomie
Selbstorganisation

beschrieben werden
DIANE Service Descriptions

zu einander kommen
halbsemantische Overlays

abgeglichen werden
DIANE Service Descriptions
Geräte müssen zur
Ressourcenbereitstellung
motiviert werden
40
Anreizschemata
Anforderungen und Lösungsansätze
Angebote und Nachfragen
müssen:
Automatisierung
Effizienzanforderungen
Autonomie
Selbstorganisation

beschrieben werden
z.B. WSDL

zu einander kommen
halbsemantische Overlays

abgeglichen werden
WSDL Vergleich, manuelle
Nachbesserung
Geräte müssen zur
Ressourcenbereitstellung
motiviert werden
41
Ad-hoc-Netze in einer Organisation,
manuelle Dienstnutzung
Anforderungen und Lösungsansätze
Angebote und Nachfragen
müssen:
Peer-to-Peer- Systeme
Automatisierung
Effizienzanforderungen
Autonomie
Selbstorganisation

beschrieben werden
DIANE Service Descriptions

zu einander kommen

abgeglichen werden
Dienstverzeichnisse, Fluten,
Overlays
DIANE Service Descriptions
Geräte müssen zur
Ressourcenbereitstellung
motiviert werden
42
Anreizschemata
DIANE: Beitrag
(Semantische) Dienstbeschreibung
M
O
T
I
V
A
T
I
O
N
Schichtung, reine Zustandsorientierung, Variablen
(Dezentrale) Dienstsuche
Overlays: Cluster, Rings, Lanes
(Effiziente) Dienstausführung
S
I
M
U
L
A
T
I
O
N
Transparente Dienstkombination
Anreize für die
Dienstsuche
43
DIANEmu
Aktivitätsbas. Benutzermodell
D
A
N
K
E
...für die Aufmerksamkeit
Alle Veröffentlichungen und den Simulator gibt es unter:
http://www.ipd.uni-karlsruhe.de/DIANE
44

ppt