PROFILI
Un sistema distribuito e decentralizzato di
profile-matching
Lorenzo Moretti
Maggio 2004
Profile-Matching

Realizzazione di un sistema di profile-matching

Dispositivo: entità fisica mobile con capacità di calcolo (anche
ridotta) e capacità di formare reti spontanee

Profilo: coppia attributo valore in cui si esplicita una qualità
attuale del dispositivo ed una qualità attesa in un dispositivo col
quale fare coppia
Proprietà P1
Attuale
Atteso
Val_A
Val_B
Proprietà P1
Match
Attuale
Atteso
Val_B
Val_A
Applicazioni

Moltissime possibili applicazioni, per lo più
inesplorate





Applicazioni di intrattenimento, come chat, incontri di
persone con gusti affini...
Ricerca di servizi in ambienti “nomadic user”
Ricerca di risorse in ambienti ostili
...
Tutto in un contesto di massimo dinamismo!
 Enfasi più sull’infrastruttura necessaria per
creare il servizio che sui possibili servizi (aspetti
algoritmici ed implementativi)
L’infrastruttura necessaria

Necessità di un supporto base per la creazione
dell’infrastruttura necessaria






Inquiry: possibilità di ricercare dispositivi nei paraggi
Discovery: capacità di rilevare l’applicazione/servizio di
profiling su un dispositivo
Send: capacità di iviare dati
Receive: capacità di ricevere dati
Naming Service: dispositivi con identificativi univoci
Sopra questa struttura, costruzione del supporto per il
routing e per il broadcast. Sopra supporto per il profilematching.
Routing
Il primo servizio di cui abbiamo bisogno è
il servizio di routing.
 Ogni dispositivo deve
avere la propria tabella
 Possibilità di raggiungere
dispositivi passando attraverso altri
dispositivi
 Necessità di fare fronte ad una rete
dinamica

Ogni dispositivo come router
Ogni dispositivo deve contenere una
tabella di routing che consenta di
determinare il percorso per raggiungere un
altro dispositivo.
 Tabella aggiornata dinamicamente grazie
al meccanismo di inquiry/discovery.
Struttura
 Struttura tabella:

ROUTINGTABLE ::= [DEVICES]
DEVICE ::= {ID ROUTINGTABLE}
DEVICES ::= DEVICE, DEVICES | empty
ricorsiva
Creazione/Aggiornamento RT
Ogni oggetto conosce i propri vicini
(inquery/discovery)...
 Ma non conosce le loro routing table!
 Le routing-table dei vicini vengono
richieste e inviate (serializzate in testo e
ricostruite).
 Aggiornamento periodico per mantenere
aggiornato il sistema (fare fronte all’arrivo
e alla partenza di dispositivi).

Calcolo dei percorsi
Ogni dispositivo conosce così tutti i
dispositivi raggiungibili.
 Possibilità calcolare a priori il percorso per
raggiungere un destinatario.
 Percorso allegato al messaggio ed
utilizzato ad ogni hop nel raggiungimento
del destinatario.
 Il percorso è calcolato una sola volta dal
mittente.

Broadcast





Operazione utile a livelli superiori (non utilizzata
nel routing).
Realizzata con TTL (Time To Live).
Possibilità di dimensionare il TTL
opportunamente osservando le routing-table.
Possibilità di creare sottogruppi (locali)
dimensionando opportunamente il TTL.
Algoritmo:


se viene ricevuto un messaggio broadcast con TTL > 0
lo si propaga a tutti i vicini (eventualmente non al
mittente) dopo avere decrementato TTL.
se TTL = 0 non lo si propaga.
Il sistema di profile-matching
Necessità di esaminare i profili e di
segnalare le affinità alla coppia di
dispositivi che fanno match
 Scelta di un solo gestore, eletto tra i
partecipanti alla rete:

 Limitazione
dei messaggi per il coordinamento
 Limitazioni dei conflitti nella gestione dei match
L’algoritmo di elezione del gestore/1


Algoritmo decentralizzato, pessimista-reattivo
Algoritmo:




ognuno aspetta richieste di profilo dal gestore alle quali risponde
inviando il proprio profilo.
se un nodo non riceve richieste per più di un certo periodo, il
nodo si auto-proclama gestore.
se il dispositivo è un gestore, invia ogni intervallo di tempo
predefinito un broadcast di richiesta del profilo (si noti che è
possibile, giocando sul time-to-live del messaggio, dimensionare
l'area di influenza del gestore).
se un gestore ottiene una richiesta di profilo da un'altro gestore
(caso di conflitto), la periferica corrente si disattiva dallo stato di
gestore solo se l'id del gestore in conflitto è lessicograficamente
maggiore della propria.
L’algoritmo di elezione del gestore/2
[keepRunning == false]
getRequest()
[keepRunning == true]
[elected == false]
[elected == true]
[reqTimeout > DELTA]
[elected == true]
elected = true
invio richiesta profili (BCAST)
[elected == false]
[non ho l'ID più alto]
elected = false
controllo match
[reqTimeout <= DELTA]
invia profilo
invio segnalazioni match
[ho l'ID più alto]
sleep
elapsedTimeout = 0
Test su J2SE

Per testare gli algoritmi è stata
implementata un ambiente di simulazione
in J2SE:
 Possibilità
di testare il routing
 Possibilità di testare l’algoritmo di elezione
Implementazione J2ME

Il sistema è stato realizzato per funzionare su
dispositivi telefoni cellulari che supportino Java
(micro edition) e Bluetooth.
 Il supporto di rete Bluetooth è stato sfruttato
tramite le API JSR-82:



Sistema non proprietario per Java
Necessita implementazioni sui telefoni dei produttori
Il sistema è stato sviluppato per sistemi Nokia
(con SDK Nokia), ma dovrebbe essere
compatibile con qualsiasi altra implementazione
JSR-82 di altri produttori.
BasicService
1
*
«interface»
RoutingTableListener
+deviceAdded()
+deviceRemoved()
RoutingTable
«interface»BasicService
+addDevice()
+removeDevice()
+getRouteTo()
+addRoutingTableListener()
+removeRoutingTableListener()
+update()
-routingTable
+getDevice()
+getDevicesInRange()
+registerListenerDevice()
+deliverMessage()
1
1
java::lang::Thread
1
«interface»
Device
+getId()
+getRoutingTable()
+receive()
RoutingManager
*
-setUpdateFrequency
-getUpdateFrequency
-devices
Aggiorna periodicamente la routing-table
Astrazione dei servizi di base per
implementare il sistema di profile-matching
 Dov’è necessaria implementazione
specifica per una tecnologia di rete, si
sono definite solo le interfaccie

Cenni sulla tecnologia Bluetooth






Struttura a stack, in gran parte
implementata on-chip
Comunicazione radio nella
frequenza 2.4GH ISM (IndustrialeScientifica-Medica), a 1MB
Studiata per bassi consumi e
dispositivi a basso potenza
computazionale
Supporto integrato per inquiry e
discovery, per favorire la nascita di
PAN (personal area network)
Possibilità di creare reti spontanee
secondo il modello PICONET e
SCATTERNET
Fornisce sia protocolli a basso
livello (L2CAP) sia protocolli
evoluti come RFCOMM
(emulazione di comunicazione
seriale)
Utilizzo del Bluetooth

Implementazione di BasicService basata sulla
tecnologia Bluetooh:



Supporto built-in per inquiry e discovery.
Utilizzo di L2CAP, protocollo di comunicazione
leggerissimo.
Sfruttato per funzionare senza connessione: una
connessione viene stabilita sono quando è necessaria
una comunicazione, dopodichè viene chiusa per non
occupare risorse, evitando così le limitazioni di
PICONET e SCATTERNET.
J2MEBasicService
J2MEBasicService
BasicService
+getDevice()
+getDevicesInRange()
+registerListenerDevice()
+deliverMessage()
J2MEBasicServiceServer

Struttura basata sulle API JSR-82
Il componente è un direttore dei lavori che incapsula al suo interno il
funzionamento di JSR-82, offrendo una nuova semantica:
java::lang::Thread




J2MEBasicServiceSender
+start()
+stopDiscovering()
+getRemoteDevices()
+start()
+stopListening()

J2MEBasicServiceDiscoverer
Send e receive con un delegato, non più semantica bloccante
Inquiry/Discovery secondo un modello non più publish-subscribe (JSR82) ma non bloccante in polling.
Funzionamento del tutto trasparente all’esterno, politiche interne
nascoste
Modello ad oggetto-attivo
Inquiry/Discovery
basicService : J2MEBasicService
server : J2MEBasicServiceServer
start
discoverer : J2MEBasicServiceDiscoverer
bloccante
start()
update
getDevicesInRange
update
getRemoteDevices
update
update
update
update
...
...
Invio e ricezione dei messaggi


Vari tipi di messaggi supportati:
 BCAST, RT_REQ,
RT_SEND, USER
Il sistema di base fornisce il
supporto per la comunicazione
delle routing-table alle altre
periferiche
bs1 : profilesj2me::J2MEBasicService
start()
bs1Server : profilesj2me::J2MEBasicService
Server
start()
bs2
bs1Discoverer : profilesj2me::J2MEBasicService
Discoverer
start()
bs2Server
in ascolto
detecting
chiedi RT al disp. trovato
send RT
start
bs1Sender : profilesj2me::J2MEBasicService
Sender
send RT_REQ
bs2Sender
start
send RT
send RT_SND
notifica nuova RT
aggiornamento tabella disp. vicini
Trasferimento degli oggetti

Necessità di trasferire le routing-table dei vari
dispositivi per formarne ricorsivamente di nuove.
 Necessità di una semantica di riferimento
remoto non fornita dal sistema.
 Si è ovviato al problema creando copie locali
delle tabelle dei dispositivi, sfruttando un
meccanismo di serializzazione/deserializzazione
creato ad-hoc.
 Si ovvia al problema della desincronizzazione
con un oggiornamento periodico continuo (un
errore è comunque tollerabile, in quanto il
sistema offre una semantica di invio may-be).