INDICE
[1] INTRODUZIONE ...5
[1.1] EVENT NOTIFICATION SERVICE E PUBLISH/SUBSCRIBE: BREVE INTRODUZIONE...5
[1.2] ODMRP: BREVE INTRODUZIONE...6
[2] PROGETTAZIONE...11 [2.1] QUALNET 3.6...11 [2.2] SOLUZIONE PROPOSTA...13 [2.3] MODELLIZZAZIONE...17 [2.3.1] Moduli ...17 [2.3.2] Publisher ...19 [2.3.3] Subscriber ...19 [2.3.4] ODPSRP...20 [2.3.4.1] Astrazione channel...21 [3] REALIZZAZIONE ...23 [3.1] PUBLISHER ...23 [3.2] SUBSCRIBER...24 [3.3] ODPSRP ...26 [3.3.1] Parametri Di Funzionamento...29 [3.3.2] JOIN QUERY ...33 [3.3.3] JOIN REPLY ...37
[3.3.4] JOIN REPLY ACK...41
[3.3.5] NOTIFICATION...42
[3.3.6] Interazione tra nodi...43
[3.3.7] Miglioramenti e Correzioni...44
[3.3.7.1] Join Query Buffer ...44
[3.3.7.2] Schedulazione JOIN REPLY ...45
[3.3.7.3] Notification Buffer...48
[3.3.7.4] BackOff Time ...49
[3.3.7.5] Passive Join Reply Acknowledgement...50
[3.3.7.6] Selezione del Path di trasporto ...52
[3.3.7.7] Join Reply Help...53
[3.3.7.8] LIGHT JOIN QUERY ...54
[3.3.7.9] Frammentazione Pacchetti ...55
[3.3.7.10] Filter Timeout e Reply Timeout...57
[3.4] QUALNETANIMATOR...59
[4] ANALISI PRESTAZIONI...65
[4.1] STATISTICHERACCOLTE ...65
[4.2] AMBIENTEDISIMULAZIONE...66
[4.3] VALUTAZIONE BACKOFFTIME ...69
[4.3.1] Notifiche di dimensioni ridotte (44byte)...70
[4.3.1.1] NOTIFICATION LOSS RATIO...70
[4.3.1.2] NOTIFICATION LATENCY ...73
[4.3.1.3] TRAFFIC OVERHEAD ...75
[4.3.1.4] DISTRIBUZIONE DELLE LATENZE...76
[4.3.1.5] Conclusioni ...78
[4.3.2] Notifiche di dimensioni maggiorate (512byte) ...78
[4.3.2.1] NOTIFICATION LOSS RATIO...79
[4.3.2.2] NOTIFICATION LATENCY ...80
[4.3.2.3] TRAFFIC OVERHEAD ...82
[4.3.3] Conclusioni ...83
[4.4] ANALISI JOIN QUERY INTERVAL...84
[4.4.1.1] NOTIFICATION LOSS RATIO ... 84
[4.4.1.2] NOTIFICATION LATENCY... 86
[4.4.1.3] TRAFFIC OVERHEAD ... 87
[4.4.2] Notifiche di dimensioni maggiorate (512 byte)...89
[4.4.2.1] NOTIFICATION LOSS RATIO ... 89
[4.4.2.2] NOTIFICATION LATENCY... 90
[4.4.3] TRAFFIC OVERHEAD...92
[4.4.4] Conclusioni ...93
[4.5] JOIN QUERY BUFFER E LIGHT JOIN QUERY...95
[4.5.1] NOTIFICATION LOSS RATIO ...95
[4.5.2] NOTIFICATION LATENCY...97
[4.5.3] TRAFFIC OVERHEAD...98
[4.5.4] Conclusioni ...99
[4.6] NOTIFICATION BUFFER E SCHEDULAZIONE JOIN REPLY...100
[4.6.1] Notification Loss Ratio...101
[4.6.2] Notification Latency...102
[4.6.3] Traffic Overhead ...103
[4.6.4] Conclusioni ...104
[4.7] CONFRONTO DI PRESTAZIONI...105
[4.7.1] Test di mobilità...105
[4.7.1.1] Notification Loss Ratio... 106
[4.7.1.2] Traffic Overhead... 109
[4.7.2] Test di scalabilità rispetto al numero di Publisher ...111
[4.7.3] Test di scalabilità rispetto al numero di pubblicazioni ...112
[5] CONCLUSIONI E SVILUPPI FUTURI...115
[6] APPENDICE ...119
[6.1] PARAMETRI ODPSRP(FILE “.CONFIG”) ...119
[6.2] INIZIALIZZAZIONE PROTOCOLLO DI SERVIZIO...121
[6.3] INIZIALIZZAZIONE APPLICAZIONI PUBLISHER...121
[6.3.1] Inizializzazione applicazioni Subscriber...121
Sommario
Nei sistemi distribuiti le applicazioni acquistano sempre più caratteristiche quali eterogeneità, asincronismo e disaccoppiamento; in un simile scenario diviene sempre più marcata la necessità di avere a disposizione un efficace ed efficiente meccanismo di interazione tra questo tipo di applicazioni.
Con Event Notification Service si intende un’infrastruttura hardware/software che permette l’interazione tra applicativi distribuiti tramite consegna di notifiche di eventi.
Il presente lavoro propone un Event Notification Service ispirato al meccanismo di funzionamento del protocollo di routing multicast ODMRP (On Demand Multicast Routing Protocol), realizzato su misura per reti wireless ad hoc.
Una rete wireless ad hoc è una rete costituita da dispositivi mobili, priva di ogni tipo di infrastruttura fissa e amministrazione centralizzata in cui la dinamicità topologica impone continue riconfigurazioni.
Il sistema progettato realizza un servizio di notifica basato sul protocollo Publish/Subscribe; inoltre è content-based e advertisement-broadcast-based: questa implementazione offre grandi vantaggi in termini di scalabilità ed efficienza in quanto permette di limitare il traffico e in alcuni casi di annullarlo in base alle effettive necessità di servizio del network.
Allo scopo di analizzare e valutare in modo più preciso le prestazioni del sistema realizzato sono state effettuate una serie di simulazioni preliminari che hanno permesso di individuare i valori critici da assegnare ai parametri di funzionamento del sistema stesso.
Dalla successiva analisi delle prestazioni effettuata tramite simulazioni comparative con il protocollo multicast ODMRP, è risultato che il sistema progettato offre in generale una maggiore efficienza ed efficacia, riuscendo in alcune situazioni a diminuire di oltre la metà il traffico totale e il numero di notifiche non correttamente consegnate.
Il migliore comportamento è particolarmente evidente nelle simulazioni effettuate con basso traffico di rete, condizione nella quale la migliore efficienza permette di ridurre drasticamente il rischio di collisioni di pacchetti.
Tutte le analisi comparative sono state eseguite non utilizzando il meccanismo di filtraggio e riduzione del traffico che la tipologia content-based del servizio permette: da quanto detto se ne deduce che le prestazioni in un caso reale di utilizzo saranno molto probabilmente superiori ed ulteriormente incoraggianti.
[1] INTRODUZIONE
Nei sistemi distribuiti le applicazioni acquistano sempre più caratteristiche quali eterogeneità, asincronismo e disaccoppiamento; in un simile scenario diviene sempre più marcata la necessità di avere a disposizione un efficace ed efficiente meccanismo di interazione tra questo tipo di applicazioni.
Con Event Notification Service si intende un’infrastruttura software che permette l’interazione tra applicativi distribuiti tramite consegna di eventi.
Di particolare interesse scientifico e pratico è lo studio di protocolli di comunicazione che permettano di sviluppare un Event Notification Service da utilizzare in reti wireless ad hoc. Per rete ad hoc si intende una rete wireless priva di ogni tipo di infrastruttura fissa e senza amministrazione centralizzata che sia capace di riconfigurarsi dinamicamente.
In un simile network le route di consegna di pacchetti sono in genere multihop a causa della limitato raggio di copertura radio dei dispositivi wireless.
Il nostro obiettivo è quello di realizzare e analizzare un servizio di notifica di eventi di tipo Publish/Subscribe per reti wireless ad hoc altamente mobili che sfrutti le elevate prestazioni e le ottime caratteristiche di robustezza, affidabilità e scalabilità offerte dal protocollo ODMRP (On Demand Multicast Routing Protocol).
A tale scopo introduciamo il modello di comunicazione Publish/Subscribe e proseguiamo col descrivere il protocollo ODMRP.
[1.1] Event Notification Service e
Publish/Subscribe: breve introduzione
Con Event Notification Service si intende un’infrastruttura hardware/software capace di erogare un servizio di consegna di notifiche di eventi tra elementi distinti di uno stesso sistema basato sul concetto astratto di interazione ad eventi.
n un simile sistema è necessario avere a disposizione un meccanismo di trasporto di notifiche di eventi che devono essere consegnate a uno o più elementi distinti.
Un Event Notification Service ha quindi lo scopo di offrire un supporto di trasporto e di consegna di queste notifiche su un qualsiasi sistema distribuito.
Il modello Publish/Subscribe rappresenta il protocollo base su cui si realizza un Event Notificatin Service.
In un modello Publish/Subscribe in particolare si possono riconoscere due tipi di utenti: • Publisher (utente che pubblica notifiche eventi inviandoli al servizio)
• Subscriber (utente che sottoscrive un certo tipo di eventi di interesse)
In un sistema distribuito possiamo pensare ai Publisher e ai Subscriber come a dei client che si interfacciano al protocollo tramite opportuni access point.
EVENT NOTIFICATION SERVICE
Publish/Subscribe Protocol Publisher Subscriber Subscriber Publisher Figura 1
I Publisher accedono al servizio notificando un evento tramite la funzione Publish(notification); i Subscriber accedono al servizio tramite le funzioni Subscribe(expression) (con la quale si sottoscrivono al servizio di notifica specificando il tipo di eventi di interesse) e Unsubscribe() (con la quale cancellano eventuali precedenti sottoscrizioni).
È opportuno a questo punto classificare tra modelli Publish/Subscribe subject-based e
content-based.
I primi sono più semplici e prevedono Subscriber che sottoscrivono il tipo di evento di interesse in base alla tipologia, non applicando quindi nessuna condizione sul contenuto di tale evento. I secondi invece prevedono la possibilità da parte del Subscriber di indicare all’interno della sottoscrizione una o più condizioni sul contenuto dell’evento.
[1.2] ODMRP: breve introduzione
ODMRP (On Demand Multicast Routing Protocol) è un protocollo multicast concepito per essere impiegato nell’ambito delle reti wireless ad hoc, nelle quali la mobilità dei nodi e la conseguente riorganizzazione topologica della rete è una attività normale e non un evento straordinario.
ODMRP è basato su una struttura a griglia (MESH) di collegamenti (a differenza di molti altri protocolli multicast che si basano invece su alberi aciclici).
Da questa scelta, che permette di avere connessioni ridondanti, deriva la forza di questo protocollo che offre maggiore affidabilità, robustezza e semplicità di riconfigurazione a scapito di un piccolo incremento di traffico operativo dovuto alle trasmissioni ridondanti.
Inoltre ODMRP utilizza quasi esclusivamente trasmissioni di tipo broadcast, sfruttando appieno le caratteristiche intrinseche del mezzo trasmissivo.
All’interno del protocollo si identificano tre entità: • SENDER
• RECEIVER • Nodi
Possiamo pensare ai sender e ai receiver come a dei nodi ODMRP particolari che generano e ricevono traffico rispettivamente, oppure come entità esterne al protocollo che si connettono come client ad un nodo ODMRP. Nel seguito utilizzeremo per semplicitá la prima visione funzionale. SENDER RECEIVER RECEIVER NODE NODE NODE NODE RECEIVER Figura 2
Dalla figura 2 è possibile osservare il funzionamento della griglia (MESH) di collegamenti: ogni Receiver ha un cammino (path di colore blu) verso il sender, ma nodi intermedi di cammini diversi possono trovarsi sufficientemente vicini da avere dei collegamenti fittizi trasversali (path di colore rosso) che rendono il trasporto più robusto e ridondante.
Ogni nuova notifica pubblicata dal Sender ricevuta dai nodi intermedi viene ritrasmessa in modo da raggiungere tutti i Receiver. Ma la presenza di questi collegamenti fittizi permette di recuperare da probabili modifiche della topologia della rete e da eventuali collisioni di pacchetti. La MESH viene periodicamente aggiornata su iniziativa dei SENDER (on demand) permettendo un continuo adattamento della stessa al layout dei nodi.
I SENDER periodicamente inviano un messaggio broadcast JOIN QUERY. L’informazione del canale multicast a cui il JOIN QUERY si riferisce é contenuta all’interno dell’header ip. Ogni nodo che riceve un JOIN QUERY non duplicato lo ritrasmette e memorizza nella propria routing table l’indirizzo del nodo di provenienza del pacchetto e il suo SENDER.
In questo modo il JOIN QUERY inonda l’intera rete.
A tale messaggio i RECEIVER rispondono dopo un certo intervallo con un messaggio broadcast JOIN REPLY all’interno del quale è presente una tabella (JOIN TABLE) contenente gli indirizzi dei nodi da cui hanno ricevuto le JOIN QUERY relative i vari SENDER.
I nodi che ricevono un pacchetto JOIN REPLY controllano se all’interno della JOIN TABLE in esso contenuta esiste un entry col loro indirizzo; in caso affermativo essi attivano il flag FG (Forwarding Group) per il canale multicast associato, in quanto realizzano di trovarsi nel
shortest forwarding path tra il receiver e il sender, divenendo membri del Forwarding Group.
Quindi dopo un opportuno intervallo inviano la loro propria JOIN REPLY contenente la propria JOIN TABLE.
Tutti i nodi appartenenti al Forwarding Group di un canale multicast si occuperanno di ritrasmettere di tutti i pacchetti non duplicati che gli perverranno su quel canale multicast.
In questo modo si crea un insieme di nodi appartenenti al Forwarding Group tali da creare un cammino minimo per ogni coppia SENDER/RECEIVER.
SENDER1
SENDER2
NODE2
RECEIVER1
RECEIVER2
NODE1 Join Table RECEIVER1
sender next node SENDER1 NODE1 SENDER2 NODE2
Join Table RECEIVER2 sender next node SENDER2 NODE2 SENDER1 NODE2
sender next node SENDER1 SENDER1 SENDER2 SENDER2 Join Table NODE2
sender next node SENDER1 SENDER1 Join Table NODE1
Figura 3
Il SENDER1 invia un proprio JOIN QUERY che raggiunge NODE1 e NODE2. Il SENDER2 invia un proprio JOIN QUERY che raggiunge NODE2.
In routing table NODE1 avremo:
sender Upstream
SENDER1 SENDER1
NODE1 ritrasmette il JOIN QUERY che raggiunge RECEIVER1.
NODE2 ritrasmette entrambi i JOIN QUERY ricevuti da SENDER1 e SENDER2 che raggiungono entrambi RECEIVER1 e RECEIVER2.
NODE1 e NODE2 attiveranno entrambi il flag FG alla ricezione del JOIN REPLY di RECEIVER1 in quanto entrambi troveranno un proprio entry nella JOIN TABLE, quindi entrambi propagheranno la propria JOIN TABLE dopo aver ricevuto il JOIN REPLY di RECEIVER2, fino a farla pervenire ai SENDER1 e SENDER2.
Entrambi i nodi intermedi quindi apparterranno al Forwarding Group e ritrasmetteranno tutti i pacchetti multicast che riceveranno. Notare che entrambi ritrasmetteranno i pacchetti provenienti dal SENDER1, quindi il RECEIVER1 riceverà entrambe le ritrasmissioni.
[2] PROGETTAZIONE
Il nostro obiettivo è quello di realizzare e analizzare un Event Notification Service con interfaccia Publish/Subscribe su una rete wireless altamente mobile che sfrutti le elevate prestazioni e le ottime caratteristiche di robustezza, affidabilità e scalabilità offerte dal protocollo ODMRP (On Demand Multicast Routing Protocol).
A tale scopo utilizzeremo l’ambiente di simulazione per reti QUALNET® 3.6.
Iniziamo introducendo tale simulatore e proseguiamo descrivendo ad alto livello il sistema che abbiamo realizzato.
[2.1] Qualnet 3.6
Qualnet 3.6 è un ambiente di simulazione molto potente che permette la progettazione, integrazione e testing di protocolli di qualsiasi tipo da inserire in simulazioni più o meno complesse al fine di valutarne comportamento ed efficacia/efficienza.
Il pacchetto Qualnet comprende: • Quanlet Simulator • Qualnet Animator • Qualnet Designer • Qualnet Analyzer • Qualnet Tracer • Qualnet Importer
In particolare noi faremo largo uso dei primi due moduli, ovvero del Qualnet Simulator all’interno del quale integreremo il nostro sistema, e del Qualnet Animator attraverso il quale potremmo visualizzare graficamente il comportamento complessivo del sistema nelle varie simulazioni.
Qualnet prevede la costruzione di simulazioni in grande dettaglio.
In primo luogo è possibile specificare il tipo di elementi hardware e software da simulare per ogni nodo, la loro interazione, nonché il layout di tali nodi nello spazio e la loro interconnessione.
Nel nostro caso i nodi di interesse saranno tutti elementi wireless, quindi nelle nostre simulazioni saranno assenti ogni tipo di interconnessione dirette tra nodi diversi.
Qualnet prevede la possibilità di personalizzare a piacimento il protocol stack, ovvero di specificare il tipo di protocollo da utilizzare ad ogni layer.
Routing
Application layer
Tranport layer
Network Layer (IP)
Physical layer Mac layer Application layer
Tranport layer
Network Layer (IP)
Physical layer Mac layer
Figura 4
Ogni protocollo è costituito da: • 1 Event Dispatcher • più Event Handler
Event Dispatcher Event 1 Handler Event 2 Handler Event 3 Handler Initialization Finalization Figura 5
All’avvio della simulazione viene chiamata la funzione di inizializzazione per ogni protocollo presente su ogni nodo. Tale funzione che si occupa di inizializzare le strutture dati del protocollo stesso.
Al termine della simulazione similmente viene eseguita una funzione di finalizzazione che provvede anche a memorizzare le statistiche del protocollo.
L’Event Dispatcher di un protocollo viene eseguito ogni volta che un nodo riceve un evento indirizzato al protocollo stesso.
A questo punto l’Event Dispatcher passa l’evento all’opportuno Event Handler. In questo modo ogni protocollo viene modellato secondo una macchina a stati rendendo la progettazione semplice e guidata.
[2.2] Soluzione Proposta
ODMRP è un protocollo di routing e come tale risiede in un apposito layer, non direttamente accessibile a livello application. Nel simulatore QualNet® esso è implementato come un network layer protocol.
In particolare un applicativo ha la possibilità di: • Registrarsi ad un canale multicast • Cancellarsi da un canale multicast • Inviare dati su un canale multicast
• ricevere dati su un canale multicast a cui è registrato
L’Event Notification Service che intendiamo realizzare al contrario risiederà a livello application: si tratterà di uno strato di servizio che ricalca il meccanismo principe di ODMRP per la costruzione e aggiornamento dei cammini di trasporto.
In particolare il sistema offrirà un servizio di notifica con protocollo Publish/Subscribe di tipo
content based, per cui si è reso necessario ampliare la semplice interfaccia gestita dal protocollo
nel seguente modo:
• publish(event_type , event_value) • subscribe(event_type , expression) • unsubscribe()
Il campo expression inserito nella funzione subscribe permetterà di definire dei vincoli sul valore degli eventi che si intendono sottoscrivere.
• Ogni nodo che intende notificare un evento produce periodicamente un JOIN QUERY (in modo simile a quanto accade in ODMRP) tramite il quale inizia il processo di costruzione e aggiornamento della griglia di trasporto
• Ogni JOIN QUERY prodotta conterrà all’interno una lista di advertisement, ovvero una lista di annunci in cui specifica il tipo di eventi che si intende pubblicare.
• Ogni nodo ritrasmette inalterata ogni JOIN QUERY non duplicata che riceve
• Ogni nodo risponde alle JOIN QUERY con JOIN REPLY soltanto se le prime contengono advertisement con intersezione non vuota rispetto agli interessi locali definiti da uno o più sottoscrizioni ricevute da applicazioni Subscriber o da altri JOIN REPLY. In caso affermativo la JOIN REPLY prodotta conterrà tali espressioni.
• Ogni volta che un nodo riceve un pacchetto JOIN REPLY a lui destinato, memorizza in una opportuna struttura locale (JOIN TABLE, in analogia con ODMRP) le espressioni in essa contenute. Quindi, dopo un certo intervallo necessario a collezionare tutti i possibili JOIN REPLY prodotti da altri nodi, invia un proprio JOIN REPLY al nodo a monte lungo il cammino verso il nodo Publisher (quello che ha generato il relativo JOIN QUERY).
• Ogni volta che un nodo riceve una notifica da una applicazione locale dopo il processo di costruzione della griglia di trasporto, provvede a trasmetterla con un opportuno pacchetto di tipo NOTIFICATION.
• Ogni volta che un nodo riceve un pacchetto NOTIFICATION non duplicato controlla se il valore dell’evento in esso contenuto corrisponde a una o più espressioni precedentemente memorizzate nella JOIN TABLE, quindi in caso affermativo procede a ritrasmettere inalterato il pacchetto.
Vediamo un esempio in Figura 6.
Le espressioni presenti nelle strutture dati di NODE1 e NODE2 saranno quindi rispettivamente: {A<1;A>10} e {B<1;B>10}.
NODE1 e NODE2 quindi trasmetteranno soltanto notifiche che soddisfino almeno una delle due espressioni, tagliando alla fonte tutti il restante traffico.
Sarà necessario impostare un timeout per ogni espressione memorizzata in ogni nodo, in modo da eliminare eventuali espressioni ricevute da nodi non più raggiungibili o non più interessati a tale servizio (e per il quale quindi non invieranno più ulteriori JOIN REPLY).
Tale timeout dovrà essere tarato con opportune simulazioni ma prevediamo che un buon valore possa corrispondere al timeout previsto per il flag FG previsto in ODMRP.
Publish A Publish B Subscr. A<1,B<1 Subscr. A>10,B>10
Join Table NODE5 sender next node NODE1
NODE2
filter NODE4
NODE3
Join Table NODE6
sender filter A<1 B<1 NODE2 B>10 NODE1 A>10 next node NODE4 NODE3 Join Table NODE4
sender filter
NODE1 NODE2
A>10 next node
Join Table NODE3
sender filter NODE1 next node NODE1 NODE1 NODE2 B>10 B<1 A<1 NODE1 NODE2 NODE6 NODE5 NODE3 NODE4 Figura 6
Come possiamo facilmente notare con questa implementazione i nodi del servizio indicano le espressioni che corrispondono ai loro interessi (subscriptions) attraverso i JOIN REPLY.
Allo stesso tempo i nodi che pubblicano eventi trasmettono le tipologie di eventi offerti tramite advertisement inseriti all’interno dei pacchetti JOIN QUERY.
Quindi siamo riusciti a combinare attraverso un unico meccanismo del tutto similare al protocollo ODMRP sia la ricostruzione dei cammini della rete sia il broadcast di advertisement e suscriptions, realizzando, con minimo sforzo e senza nessun aumento di traffico in termine di numero di pacchetti, un meccanismo advertisement broadcast simile a quello descritto in SIENA (articolo [1]).
La soluzione è altamente scalabile dal punto di vista di traffico generato sulla rete infatti le espressioni memorizzate nei nodi della rete permettono di tagliare il traffico laddove non è di interesse e il più vicino possibile alla fonte.
Nel caso una notifica non sia di interesse a nessuno (abbia una intersezione vuota con ogni espressione sottoscritta nel sistema) verrà addirittura tagliata alla fonte dal sistema, senza generare nessun traffico inutile.
Il nuovo sistema così progettato rappresenta un’ottima soluzione che ben si presta a realizzare un servizio best effort su reti wireless altamente mobili.
Le applicazioni PUBLISHER e SUBSCRIBER inoltre sono molto semplici e si limitano a pubblicare notifiche nel primo caso e a sottoscrivere una espressione nell’altro.
Il servizio offerto sarà advertising broadcast based, ovvero i nodi pubblicatori provvederanno a inondare la rete con advertisement contenenti i tipi di eventi pubblicati.
[2.3] MODELLIZZAZIONE
Descriviamo di seguito ad alto livello il sistema che andremo a realizzare.
Iniziamo con l’introdurre l’ambiente di simulazione Qualnet® all’interno del quale realizzeremo il protocollo di servizio e tramite il quale effettueremo le valutazioni di prestazione.
[2.3.1] Moduli
Il sistema publish/subscribe da realizzare è costituito fondamentalmente da tre moduli: • il publisher
• il subscriber
• lo strato di servizio Publish/Subscribe
Lo strato di servizio è il modulo principale del nostro progetto ed è realizzato all’interno dell’application layer come una applicazione vera e propria a cui si interfacciano le applicazioni publisher e subscriber.
Tale strato di servizio lo chiameremo ODPSS (On Demand Publish Subcribe Service). Il publisher è un’applicazione che si limita a inviare notifiche di eventi al servizio ODPSS. Il subscriber è un’applicazione che sottoscrive un certo tipo di eventi eventualmente con un filtro (es. “subscribe x>0” significa che il subscriber si sottoscrive per tutti gli eventi di tipo x con valore maggiore di 0).
Il subcriber può quindi cancellare le sue sottoscrizioni.
Il servizio ODPSS si occuperà di trasportare tutte le notifiche pubblicate dai publishers a tutti i subscribers interessati.
O D P S S
Publisher Subscriber publish x=3 subscribe x>0 X=3 unsubscribe Figura 7In Figura 7 possiamo vedere una rappresentazione grafica schematica dell’interfaccia a disposizione delle applicazioni Publisher e Subscriber.
Il servizio di trasporto delle notifiche ODPSS verrà implementato all’interno di un protocollo di routing apposito che chiameremo ODPSRP (On Demand Publish Subscribe Routing Protocol). Tutto questo risiederà quindi all’interno dell’application layer.
Application Layer
Publisher
ODPSRP
Subscriber
Figura 8
Tutti i nodi della rete wireless che supporteranno il servizio avranno quindi una istanza di ODPSRP, mentre qualsiasi nodo potrà avere un numero arbitrario di istanze di Publisher e Subscriber.
node4
Application layer Subscriber “X>10”node2
node3
Application layer Publisher “X”node1
Application layer Publisher “X” Publisher “Y” Subscriber ”X>0” Application layer Subscriber “X” Subscriber “Y>0”node5
Figura 9Ad esempio potremmo avere una semplice rete come rappresentato in Figura 9, costituita da cinque nodi in cui il nodo 1 e il nodo 3 contengono pubblicatori mentre i nodi 1, 4 e 5 contengono sottoscrittori.
Il nodo 2 in questo caso sarà un puro e semplice fornitore di servizio.
[2.3.2] Publisher
Il Publisher che andremo a realizzare sarà molto semplice e si limiterà a pubblicare eventi di un certo tipo inviandoli allo strato di servizio ODPSS.
Nel nostro progetto il Publisher pubblicherà eventi con valori random a intervalli random, questo al fine di poter analizzare appropriatamente il comportamento del protocollo sotto diverse condizioni di carico.
Publisher
X=3
O D P S S
Figura 10
[2.3.3] Subscriber
Il Subscriber sarà anch’esso molto semplice e si limiterà a sottoscrivere un certo tipo di eventi con una eventuale condizione sui valori, quindi a cancellare la propria sottoscrizione.
Subscriber
O D P S S
subscribe X>0 X=3
Unsubscribe
[2.3.4] ODPSRP
Il protocollo ODPSRP che realizza il servzio ODPSS è costituito da un’applicazione presente su tutti i nodi che supportano il servizio stesso.
L’interazione tra i vari nodi si puo sintetizzare nell’invio dei seguenti tipi di messaggi: • JOIN QUERY
• JOIN REPLY • NOTIFICATION
JOIN QUERY: viene inviato periodicamente in broadcast da nodo che riceve notifiche
pubblicate da Publishers locali, che chiameremo nodo Publisher. Ogni nodo che riceve un JOIN QUERY non duplicato lo ritrasmette in broadcast in modo che questo inondi l’intera rete. All’interno di tale pacchetto sono presenti una lista di notifiche pubblicate dai publishers e in coda una lista di advertisement, ovvero un elenco di tutti i tipi di eventi che il nodo pubblica. Tramite l’invio di questo pacchetto in tutta la rete si costruiscono tutti i cammini (path) che collegano ogni nodo al nodo pubblicatore.
JOIN REPLY: viene inviato da nodi contenenti applicazioni Subscriber, che chiameremo nodi
Subscriber, in risposta al JOIN QUERY. Quindi tutti i pacchetti JOIN REPLY ricevuti
da nodi intermedi che si trovano sul cammino verso il nodo Publisher verranno ritrasmessi. All’interno questo pacchetto contiene una lista di tutti i filtri da sottoscrivere al nodo Publisher.
NOTIFICATION: ogni notifica ricevuta da un nodo Publisher da applicazioni Publisher locali
viene trasmessa in broadcast all’interno di tali pacchetti soltanto se l’evento in essa contenuto è stato sottoscritto tramite JOIN REPLY da almeno un nodo. Inoltre ogni nodo intermedio che riceve un simile pacchetto lo ritrasmette nel caso l’evento in esso contenuto soddisfi almeno un filtro ricevuto precedentemente all’interno di JOIN REPLY.
Il protocol stack che utilizzeremo sarà così costituito: • UDP (transport layer)
• IP (network layer) • 802.11b (mac layer) • 802.11b (physical layer)
Si è scelto di utilizzare UDP come transport layer in quanto la quasi totalità di pacchetti del protocollo sarà inviata in broadcast e per evitare di introdurre traffico non necessario e non
desiderato dovuto ad esempio a pacchetti di acknowledgement inseriti da altri protocolli come ad esempio il TCP.
I JOIN REPLY possono essere inviati indifferentemente in unicast o in broadcast, unica condizione è che nel secondo caso all’interno del pacchetto vi sia indicato il nodo che deve processare tale pacchetto, ovvero il nodo precedente sul path che collega il nodo publisher al nodo subscriber.
Per lo stesso motivo si può utilizzare qualsiasi protocollo di routing dato che tutti i pacchetti saranno inviati in broadcast esclusi alcuni eventuali pacchetti di acknowledgement che saranno inviati in unicast. In questi ultimi casi comunque ancora non ha importanza il tipo di protocollo di routing in quanto tali pacchetti saranno inviati soltanto a nodi vicini, ovvero entro la zona di copertura dell’antenna wireless di ogni dispositivo.
Nel nostro caso si è deciso di utilizzare come protocollo di routing AODV per la sua semplicità. In Figura 12 è riportato un semplice esempio che mostra i pacchetti scambiati dal sistema durante la fase di costruzione della rete di trasporto delle notifiche.
ODPSRP NODO INTERMEDIO U D P QUERY (X) ODPSRP NODO INTERMEDIO U D P NODO PUBLISHER Publisher publish x=3 ODPSRP U D P NODO SUBSCRIBER Subscriber X>0 ODPSRP x=3 U D P QUERY (X) REPLY (X>0) QUERY (X) REPLY (X>0) Figura 12
[2.3.4.1] Astrazione channel
Si è deciso di progettare il servizio mappandolo su canali virtuali (che indicheremo nel seguito come channel), in modo da avere la possibilità di avere una ulteriore separazione virtuale tra diverse tipologie di eventi pubblicati da publisher diversi.
Ad esempio potremmo pensare di mappare sul channel 1 tutte le notifiche relative ad eventi sportivi e sul channel 2 tutte le notifiche relative alle quotazioni di borsa, e cosi via.
Ogni channel virtuale viene gestito dal protocollo di servizio ODPSRP come una sorta di rete a parte, completamente autonoma dalle altre, quindi per ogni channel avremo personali JOIN QUERY che seguiranno un proprio indipendente meccanismo di scheduling, di refresh e di costruzione dei path.
Ovviamente questa astrazione non aggiunge nulla al servizio dato che ogni evento è già identificato dalla coppia <nome,valore> (es “X=3”), inoltre la gestione contemporanea di più
channel realizzata come reti virtualmente indipendenti crea ovviamente un overhead di
funzionamento del protocollo in quanto vengono creati pacchetti JOIN QUERY e JOIN REPLY e vengono costruiti cammini di consegna delle notifiche che solo locali rispetto al singolo
[3] REALIZZAZIONE
[3.1] PUBLISHER
Dal file di configurazione delle applicazioni (“nomefile.app”) è possibile aggiungere applicativi PUBLISHER a qualsiasi nodo tramite la stringa:
ODPSS_PUBLISHER <node> <channel> <name> <valuemin> <valuemax> <type={INT,STRING}> <starTime> <endTime> <intervalMin> <intervalMax>
Il publisher verrà quindi istanziato sul nodo <node> con questi parametri:
• channel: è il canale virtuale su cui le notifiche verranno inoltrate • name: è il nome del tipo di evento pubblicato
• valuemin,valuemax: rappresentano il range di valori che l’evento può assumere. Tali valori vengono generati in maniera casuale utilizzando la funzione rand() della libreria
“stdlib”.
• type: rappresenta il tipo di dato dell’evento. Questo puo infatti essere una stringa o un valore intero.
• startTime: rappresenta il tempo della simulazione in cui il publisher deve attivarsi e iniziare a pubblicare eventi.
• entTime: rappresenta il tempo della simulazione in cui il publisher si
disattiva e termina di pubblicare eventi.
• intervalMin,intervalMax: rappresentano il range di valori entro cui viene selezionato in modo casuale l’intervallo che intercorre tra ogni singola pubblicazione
A partire da <startTime> quindi il publisher pubblicherà eventi con una frequenza media di
(
)
/21
n IntervalMi x
IntervalMa + eventi al secondo.
Gli eventi vengono quindi inviati allo strato di servizio ODPSS tramite la funzione di libreria
MESSAGE_Send() supportata da QUALNET® 3.6.
Il messaggio inviato è di tipo ODPSS_NOTIFICATION.
Publisher
O D P S S
name value type channel X 3 INT 1 ODPSS_NOTIFICATION Figura 13
[3.2] SUBSCRIBER
Dal file di configurazione delle applicazioni (“nomefile.app”) è possibile aggiungere applicativi SUBSCRIBER a qualsiasi nodo tramite la stringa:
ODPSS_SUBSCRIBER <node> <channel> <name> <operand> <value> <type={INT,STRING}> <starTime> <endTime>
Il subscriber verrà quindi istanziato sul nodo <node> con questi parametri:
• channel: è il canale virtuale su cui si sottoscrivono le notifiche di interesse • name: è il nome del tipo di evento di interesse
• operand: è l’operando matematico che viene utilizzato per specificare il range di valori degli eventi che sono di interesse. Ad esempio è possibile sottoscrivere tutti quegli eventi di tipo “X” che soddisfano la condizione “X>0”.
Gli operandi utilizzabili sono i seguenti:
•
“<“
(solo gli eventi con valore minore di value verranno sottoscritti) •“<=“
(solo gli eventi con valore minore o uguale a value verranno sottoscritti) •“>”
(solo gli eventi con valore maggiore di value verranno sottoscritti) •“>=”
(solo gli eventi con valore maggiore o uguale di value verrannosottoscritti)
•
“==”
(solo gli eventi con valore identico a value verranno sottoscritti)•
“!=”
(solo gli eventi con valore diverso da value verranno sottoscritti) •“>=<”
(tutti gli eventi con qualsiasi valore verranno sottoscritti)• value: è il valore utilizzato nella sottoscrizione
• type: rappresenta il tipo di dato dell’evento. Questo puo infatti essere una stringa o un valore intero.
• startTime: rappresenta il tempo della simulazione in cui il subscriber invia la propria sottoscrizione.
• endTime: rappresenta il tempo della simulazione in cui il subscriber invia la propria cancellazione di sottoscrizione.
Allo scadere di <startTime> il subscriber invierà un messaggio di tipo ODPSS_SUBSCRIPTION come rappresentato in Figura 14.
Subscriber
O D P S S
name operand type
channel X > INT 1 ODPSS_SUBSCRIPTION value 0 Figura 14
A partire da <startTime> quindi il subscriber sarà sottoscritto a tutti gli eventi di nome “name” e tipo “type” con valore che soddisfa la condizione imposta da “operand” e “value”.
Da questo momento ci riferiremo a questa condizione come al filtro imposto sulle notifiche di tipo {“name”,”type”}.
Ad esempio una sottoscrizione del tipo rappresentata di seguito verrà riferita come il filtro X>0
imposto sul channel 1 con valori INTERI.
channel name operand value type
1 X > 0 INT
Allo scadere di endTime il subscriber invierà un messaggio di tipo ODPSS_UNSUBSCRIPTION allo strato di servizio ODPSS senza nessun parametro; da questo momento il filtro precedentemente sottoscrito e registrato all’interno del protocollo ODPSRP verrà invalidato e cancellato.
Subscriber
O D P S S
ODPSS_UNSUBSCRIPTION
Figura 15
Durante il normale funzionamento lo strato di servizio ODPSS invierà eventuali notifiche di eventi che corrispondano al filtro precedentemente sottoscritto dal subscriber tramite messaggi di tipo ODPSS_NOTIFICATION come rappresentato in Figura 16.
Subscriber
O D P S S
name value type
X 3 INT
ODPSS_NOTIFICATION
Figura 16
[3.3] ODPSRP
Dal file di configurazione delle applicazioni (“nomefile.app”) è possibile inizializzare lo strato di servizio ODPSS realizzato all’interno dell’applicazione ODPSRP tramite la stringa:
ODPSRP <node> <nodeEnd>
L’applicazione e quindi il servizio verranno inizializzati su tutti i nodi nell’intervallo [<node>,<nodeEnd>]. Questa scelta è stata fatta al fine di evitare di dover inserire una riga di inizializzazione per ogni nodo (se ad esempio abbiamo una simulazione con 50 nodi avrei dovuto inserire una riga di inizializzazione per ognuno dei 50 nodi nel file “nomefile.app”), e al tempo stesso per lasciare la possibilità di creare simulazioni in cui alcuni nodi non supportano il servizio.
L’applicazione riceve messaggi dai publisher e subscriber istanziati nello stesso nodo: tali messaggi (gia definiti nei precedenti paragrafi) possono essere di tre tipi:
• ODPSS_SUBSCRIPTION • ODPSS_UNSUBSCRIPTION
Quindi invia notifiche ai subscriber locali tramite messaggi del tipo: • ODPSS_NOTIFICATION ODPSS O D P S R P Subscriber Publisher ODPSS_NOTIFICATION ODPSS_NOTIFICATION ODPSS_SUBSCRIPTION ODPSS_UNSUBSCRIPTION Figura 17
Le applicazioni ODPSRP presenti sui vari nodi dialogano tramite i seguenti tipi di pacchetti UDP:
• JOIN QUERY contiene gli advertisement delle pubblicazioni ed è
responsabile della costruzione della mesh
• JOIN REPLY contiene i filtri sottoscritti e viene inviato in risposta a una JOIN QUERY soltanto se questa contiene advertisement di interesse
• JOIN REPLY ACK viene usato per inviare un acknowledgement in risposta alla ricezione di un JOIN REPLY
NODE2 UDP network ODPSS O D P S R P Subscriber NODE1 ODPSS O D P S R P Publisher X=3 JOIN QUERY (X) JOIN REPLY (X>0)
JOIN REPLY ACK NOTIFICATION (X=3)
Figura 18
Ogni pacchetto è costituito da una intestazione (ODPSRP_HEADER) e da una parte dati. L’intestazione è costituita dai seguenti campi:
• type (char) • channel (int) • nodeId (NodeAddress) • sequence (int) • hopCount (NodeAddress) • size (int) ODPSRP_HEADER DATA channel
type nodeId sequence size hopCount ...
Figura 19
Il campo type indica il tipo di pacchetto che segue. In particolare esso contiene: • ‘Q’ in caso di JOIN QUERY
• ‘R’ in caso di JOIN REPLY • ‘A’ in caso di JOIN REPLY ACK • ‘N’ in caso di NOTIFICATION
Il campo channel contiene il canale virtuale a cui il pacchetto si riferisce.
Il campo nodeId contiene l’identificatore del nodo in cui risiede il pubblicatore che ha causato la creazione del pacchetto, ovvero il nodo pubblicatore. Se ad esempio il nodo 1 pubblica un
evento, il nodo 1 invierà un JOIN QUERY con nodeId=1. A questo punto ogni nodo ritrasmetterà il JOIN QUERY lasciando tale campo inalterato.
I nodi interessati agli advertisement contenuti nel JOIN QUERY risponderanno con un JOIN REPLY lasciando inalterato il campo nodeId; i nodi intermedi faranno recapitare il JOIN REPLY al nodo creatore del JOIN QUERY, ovvero al nodeId stesso.
Anche nelle notifiche il nodeId viene riempito dal nodo pubblicatore e viene lasciato inalterato ad ogni ritrasmissione da parte dei nodi intermedi che si trovano sul cammino (path) verso i sottoscrittori interessati finchè queste non giungono sui nodi sottoscrittori stessi.
Il campo sequence viene usato assieme ai campi channel e nodeId per identificare univocamente un pacchetto nella rete. Esso infatti viene riempito dal nodo pubblicatore con un nuovo valore ad ogni invio di JOIN QUERY e NOTIFICATION mentre tutti i pacchetti JOIN REPLY e JOIN REPLY ACK contengono lo stesso valore relativo al JOIN QUERY a cui si riferiscono.
Il campo size contiene la dimensione in byte dell’intero pacchetto, compresa l’intestazione. Il campo hopCount viene utilizzato nei pacchetti di tipo JOIN QUERY per memorizzare la distanza in termini di salti dal nodo pubblicatore. Quindi ogni nodo che riceve una JOIN QUERY non duplicata la ritrasmette con questo campo incrementato.
Nei pacchetti JOIN REPLY invece tale campo contiene l’identificatore del nodo che si trova a monte del path che collega il nodo sottoscrittore al nodo pubblicatore. Notare che nel sistema tutti i nodi che si trovano nel cammino tra il pubblicatore e il sottoscrittore diventano dei sottoscrittori loro stessi, infatti essi sottoscrivono i filtri ricevuti da JOIN REPLY al nodo superiore fintanto che questi non scadono a causa di un opportuno timeout (vedi ODPSRP_FG_TIMEOUT nella sezione [3.3.7.10]).
[3.3.1] Parametri Di Funzionamento
I parametri di funzionamento dello strato di servizio ODPSS sono molti: riportiamo di seguito un elenco • ODPSRP_QUERY_INTERVAL • ODPSRP_ADVERTISEMENT_LIFETIME • ODPSRP_FG_TIMEOUT • ODPSRP_QUERY_BUFFER_INTERVAL • ODPSRP_WAIT_FOR_REPLY_INTERVAL • ODPSRP_PATH_FACTOR • ODPSRP-BUFFER-FLUSH-DELAY
• ODPSRP_MAX_HOPCOUNT • ODPSRP_REPLY_ACK_TIMEOUT • ODPSRP_MAX_REPLY_RETRASMISSION • ODPSRP_MAX_BACKOFF • ODPSRP_HOP_SHORTEST_PATH • ODPSRP_QUERY_METHOD • ODPSRP_REPLY_METHOD • ODPSRP_UNICAST_REPLY_ACK • ODPSRP_SEED • ODPSRP_REPLY_HELP • OdpssStringNameSize, OdpssStringValueSize
ODPSRP_QUERY_INTERVAL: è l’intervallo che intercorre tra l’invio di ogni nuovo pacchetto JOIN QUERY. Reti particolarmente mobili richiedono un valore basso in modo da innescare il meccanismo di ricostruzione della mesh di frequente. Ciò nonostante questo provoca un aumento del traffico dovuto proprio al flooding dei pacchetti JOIN QUERY e all’invio dei pacchetti JOIN REPLY successivamente. Quindi valori troppo piccoli possono causare congestione, mentre valori più grandi garantiscono migliori prestazioni di traffico soprattutto per reti più stabili. Valori tipici si aggirano tra i 10 e i 20 secondi per reti con mobilità ridotta (non più di 5 m/s per nodo). Il nostro protocollo gestisce un valore statico di questo parametro mentre molto interessante sarebbe un approccio dinamico in cui il valore viene aggiustato runtime in base a informazioni riguardanti la stabilità della rete stessa.
ODPSRP_ADVERTISEMENT_LIFETIME: è il tempo di vita di un advertisement. Ogni volta che un Publisher pubblica un evento di un certo tipo (ad esempio “X=3”) il nodo pubblicatore genera un advertisement (“X”) incapsulato in tutti i successivi invii di pacchetti JOIN QUERY fino al tempo limite specificato da questo parametro. Oltre tale periodo il tipo di evento non viene più pubblicizzato. Un valore elevato di questo parametro diminuisce la probabilità che un evento pubblicato da un nodo necessiti di un apposito JOIN QUERY diminuendo quindi la congestione della rete. Allo stesso tempo un valore troppo elevato causa una persistenza nei pacchetti JOIN QUERY e quindi nella rete di advertisement ormai vecchi e non più utilizzati a cui i subscriber rispondono con pacchetti JOIN REPLY che vanno inutilmente ad aumentare il traffico totale.
ODPSRP_FG_TIMEOUT: è il tempo di sopravvivenza di un filtro sottoscritto da un altro nodo. Quando un nodo Subscriber riceve un JOIN QUERY con advertisement di interesse, invia un JOIN REPLY al nodo superiore del cammino (path) che collega il nodo stesso al nodo che ha generato il JOIN QUERY. Tale JOIN REPLY contiene una lista di filtri che verranno sottoscritti al nodo superiore. Il nodo superiore memorizza tutti questi filtri e provvede a ritrasmettere un proprio JOIN REPLY con tutti i filtri ricevuti e i filtri sottoscritti da subscriber locali al proprio nodo superiore nel path. I filtri ricevuti hanno un tempo di vita limitato proprio dal parametro ODPSRP_FG_TIMEOUT: oltre tale tempo vengono considerati scaduti e quindi cancellati e non più sottoscritti al nodo superiore. In questo modo tale parametro permette di invalidare cammini ormai inutilizzati e di disattivarli. È necessario che tale valore sia superiore a ODPSRP_QUERY_INTERVAL altrimenti i filtri diventano invalidi prima di un nuovo ciclo di costruzione della mesh. Un valore elevato garantisce che la perdita (non ricezione) di JOIN QUERY non comprometta il servizio di trasporto di notifiche fino ai nodi subscriber, ma al tempo stesso può essere causa di un aumento di traffico inutile causato da cammini ormai inutili ma non ancora invalidati.
ODPSRP_QUERY_BUFFER_INTERVAL: per questo parametro fare riferimento alla sezione
[3.3.7.1]
.ODPSRP_WAIT_FOR_REPLY_INTERVAL: per questo parametro fare riferimento alla sezione
[3.3.7.2]
.ODPSRP_PATH_FACTOR: per questo parametro fare riferimento alla sezione
[3.3.7.2]
.ODPSRP-BUFFER-FLUSH-DELAY: per questo parametro fare riferimento alla sezione [3.3.7.9].
ODPSRP_MAX_HOPCOUNT: è il numero Massimo di salti che un qualsiasi pacchetto può effettuare prima di essere scartato. La presenza di pacchetti scartati con questo meccanismo è indice della presenza di un errore nel protocollo e potrà essere utilizzata come informazione di debugging.
ODPSRP_REPLY_ACK_TIMEOUT: è il tempo oltre il quale scatta il timeout in caso di mancata ricezione di acknowledgement in seguito all’invio di un pacchetto JOIN REPLY. Viene utilizzato soltanto nel caso in cui la simulazione venga eseguita in modalità broadcast o in modalità unicast con ACKNOWLEDGEMENT (vedi sezione
[3.3.3]
).ODPSRP_MAX_REPLY_RETRASMISSION: è il numero massimo di ritrasmissioni di JOIN REPLY che non hanno ricevuto un acknowledgement. Anche questo parametro viene utilizzato soltanto nel caso di simulazioni eseguite in modalità broadcast o unicast con ACKNOWLEDGEMENT (vedi sezione
[3.3.3]
).ODPSRP_MAX_BACKOFF: per questo parametro fare riferimento alla sezione
[3.3.7.4]
.ODPSRP_HOP_SHORTEST_PATH: per questo parametro fare riferimento alla sezione
[3.3.7.6]
.ODPSRP_QUERY_METHOD: tramite questo parametro è possibile attivare o disattivare il meccanismo delle LIGHT QUERY dettagliato nella sezione [3.3.7.8].
ODPSRP_REPLY_METHOD: questo parametro può essere impostato con due valori: BROADCAST e UNICAST. Nel primo caso tutti i pacchetti JOIN REPLY verranno inviati in modalità broadcast e l’indirizzo del nodo destinatario verrà inserito all’interno dell’intestazione. Nel secondo caso i pacchetti JOIN REPLY verranno inviati direttamente in unicast al nodo destinatario. Per ulteriori dettagli fare riferimento alla sezione
[3.3.3]
.ODPSRP_UNICAST_REPLY_ACK: tramite questo parametro è possibile decidere se attivare o meno il meccanismo di acknowledgement in unicast per i pacchetti JOIN REPLY. Il parametro può essere settato con due valori: {YES,NO}. Se il valore è YES, ogni nodo che riceve un JOIN REPLY a lui diretto, risponde al mittente con un opportuno messaggio di acknowledgement inviato in unicast. In caso contrario nessun acknowledgement viene inviato; in questo modo il nodo subscriber non verrà mai a conoscenza di eventuali JOIN REPLY non ricevuti correttamente. Ciononostante nel caso si operi con JOIN REPLY inviate in modalità broadcast è implementato un meccanismo di Passive Reply Acknowledgement dettagliato nella sezione [3.3.7.5]
ODPSRP_SEED: si tratta di un numero tramite il quale viene inizializzata la funzione generatrice di numeri casuali rand() del linguaggio C. Tale funzione infatti genera una sequenza di numeri pseudo-casuali che dipendono dal valore di inizializzazione. Utilizziamo tale funzione principalmente per generare eventi in maniera casuale, quindi è necessario avere la possibilità di poter cambiare questo parametro ad ogni simulazione che vogliamo generare.
ODPSRP_REPLY_HELP: si tratta di un meccanismo di recupero da eventuali situazioni di malfunzionamento del meccanismo di costruzione della mesh di trasporto. Per ulteriori dettagli fare riferimento alla sezione [3.3.7.7].
OdpssStringNameSize: è la lunghezza massima del nome del tipo di evento che il sistem supporta. Di default tale valore è impostato a 16 caratteri.
OdpssStringValueSize: è la lunghezza massima del valore del tipo di evento che il sistema supporta. Di default tale valore è impostato a 16 caratteri.
OdpsrpPayloadSize: definisce la dimensione delle notifiche che vengono utilizzate nel simulatore. Notare che la dimensione delle notifiche non può scendere oltre un limite definito dalla dimensione del parametro OdpssStringNameSize e OdpssStringValueSize.
Tutti questi parametri si possono impostare dal file di configurazione della simulazione (file “.config”), fatta eccezione per gli ultimi tre (OdpssStringNameSize, OdpssStringValueSize,
OdpssPayloadSize) che al contrario sono definiti all’interno del file “odpsrp.h”.
Per modificarli è quindi necessario editare tale file e ricompilare il simulatore.
Il motivo di questa scelta è semplice e risiede nel fatto che si tratta di parametri che non influenzano il funzionamento del protocollo stesso.
[3.3.2] JOIN QUERY
I pacchetti JOIN QUERY vengono periodicamente inviati dai nodi pubblicatori al fine di aggiornare e ripristinare la mesh che garantisce il trasporto delle notifiche.
Quando lo strato di servizio ODPSS, e quindi l’applicazione ODPSRP, riceve una pubblicazione da un Publisher locale, controlla se il tipo di evento è gia stato pubblicizzato da precedenti advertisement contenuti in JOIN QUERY generate precedentemente dal nodo stesso.
In caso affermativo viene controllato che tale JOIN QUERY non sia scaduto, ovvero che il tempo trascorso dall’ultimo invio sia minore di ODPSRP_QUERY_INTERVAL.
Se l’ultimo JOIN QUERY generato non è scaduto l’evento viene direttamente inviato in broadcast tramite un pacchetto di tipo NOTIFICATION, altrimenti è necessario generare una nuova JOIN QUERY.
Il pacchetto JOIN QUERY è cosi composto: • HEADER • PAYLOAD o n_notification o notification1 o notification2 o …
o n_advertisement o advertisement1 o advertisement2 o … ODPSRP_HEADER DATA notif1 n notification
... notif2 ... advertisementn advert1 advert2 ...
Figura 20
Una JOIN QUERY quindi trasporta più notifiche e più advertisement.
Un notifica è costituita dalla coppia {<name>,<value>}, dove <name> è il tipo di evento e <value> è il valore di tale evento (es. {X,3})
Un advertisement è costituito dal solo elemento {name} che indica il tipo di evento che si pubblicizza.
Ogni volta che il servizio riceve una notifica locale (da un Publisher presente su quel nodo), il tipo di evento (<name>) viene inserito, se non ancora presente, tra la lista degli advertisement locali che il nodo pubblicizza.
Ogni elemento di questa lista ha un tempo di vita limitato, in particolare un advertisement locale scade e viene quindi eliminato e non più pubblicizzato dopo un tempo pari a ODPSRP_ADVERTISEMENT_LIFETIME dall’ultima pubblicazione.
Nella Figura 21 è riportato un esempio di funzionamento: la linea rossa rappresenta una timeline mentre gli eventi generati dal Publisher giungono in istanti diversi allo strato di servizio.
Nell’esempio sono stati usati i seguenti valori: • JOIN_QUERY_INTERVAL = 20 secondi • ADVERTISEMENT_LIFETIME = 40 secondi
All’istante 0 il Publisher pubblica “X=1”: si tratta della prima pubblicazione di un simile tipo di evento quindi viene generata un’opportuna JOIN QUERY.
Il nuovo evento “Y=2” è generato successivamente quando ancora l’ultimo JOIN QUERY non è ancora scaduto. Ma il precedente JOIN QUERY non pubblicizzava eventi di tipo “Y”, quindi è necessario inviare un nuovo JOIN QUERY contenente la notifica “Y=2” e gli advertisement {“X”,”Y”}.
NETWORK
NODE 1
O D P S R P PUBLISHER 00.00.00 00.01.20 Query X=6 [X,Y,Z] Z=5 Query Z=5 [Y,Z] 00.00.08 - 00.00.28 Join Query Interval00.00.30 - 00.00.50 Join Query Interval
Y=4 Query Y=4 [X,Y] Y=3 Notification Y=3 Y=2 Query Y=2 [X,Y] 00.00.30 - 00.01.10 Advertisement lifetime (Y) 00.00.00 - 00.00.39
Advertisement lifetime (X)
X=1
00.00.53 - 00.01.13 Join Query Interval
X=7 Query X=7 [X,Z] Query X=1 [X] X=6 Figura 21
Come possiamo vedere la notifica “Y=3” giunge al protocollo ODPSRP quando ancora il precedente JOIN QUERY (“Y=2”) non è scaduto. Quindi tale notifica viene direttamente inviata al network come pacchetto NOTIFICATION.
La notifica “Y=4” al contrario giunge dopo che l’ultimo JOIN QUERY è scaduto, quindi viene inviata una nuova JOIN QUERY: in tale query viene pubblicizzato anche “X” in quanto non è ancora trascorso un tempo superiore a ODPSRP_ADVERTISEMENT_LIFETIME dall’ultimo invio di notifiche relative a quel tipo di evento.
La notifica “Z=5” al contrario giunge dopo che l’advertisement per “X” è spirato, mentre “Y” è ancora valido. E’ comunque necessario inviare un JOIN QUERY in quanto si tratta della prima notifica dell’evento di tipo “Z”; in questo caso il pacchetto generato conterrà quindi i soli advertisement {“Y”,”Z”}
La notifica “X=6” giunge allo strato di servizio dopo che l’ultimo advertisement per “X” è scaduto, quindi è necessario inviare una JOIN QUERY.
La notifica “X=7” giunge dopo che il precedente JOIN QUERY è scaduto, quidi anche questa necessita di un opportuno JOIN QUERY. Da notare è il fatto che entrambe le notifiche “X=6” e “X=7” generano JOIN QUERY contenenti un advertisement per Z, mentre la seconda non contiene l’advertisement per Y in quanto scaduto.
Ricordiamo che i pacchetti JOIN QUERY generati da un nodo vengono ritrasmessi inalterati da tutti i nodi della rete, raggiungendo quindi tutti i subscriber presenti.
E’ opportuno osservare che tali pacchetti costituiscono un costo aggiuntivo (un overhead) al servizio di notifica che è costretto a utilizzarli per creare i cammini di consegna; al tempo stesso è bene osservare che tali pacchetti trasportano essi stessi delle notifiche che possono risultare sottoscritte e quindi di interesse anche a molti subscriber sparsi nella rete. In questo modo quindi compensiamo parte del costo dovuto al flooding di pacchetti JOIN QUERY con il trasporto di notifiche di interesse. Inoltre, dato che ogni nodo ritrasmette ogni JOIN QUERY non duplicata, abbiamo una probabilità molto elevata che le notifiche in esse contenute arrivino a tutti i subscriber della rete.
Ogni nodo che riceve un pacchetto JOIN QUERY non duplicato, oltre a ritrasmetterlo, aggiorna la propria tabella di routing del servizio ODPSS con il nodo di provenienza.
Chiameremo questa tabella TABELLA DI FORWARD ODPSRP.
In particolare, se il nodo3 riceve un pacchetto JOIN QUERY relativo al nodo1 inviato dal nodo2, aggiornarà la propria tabella in questo modo:
NodeSource NodeUp
… … Node1 Node2
… …
TABELLA DI FORWARD ODPSRP
In questo modo il nodo3 conosce il proprio cammino per raggiungere il nodo1 e può utilizzarlo in seguito nel caso di ricezione di JOIN REPLY relativi tale nodo.
[3.3.3] JOIN REPLY
Ogni nodo che riceve un pacchetto JOIN QUERY contenente advertisement di interesse, produce e trasmette un pacchetto JOIN REPLY indirizzato al nodo superiore lungo il path, ovvero al nodo da cui ha ricevuto il JOIN QUERY stesso.
Il pacchetto JOIN REPLY è così composto: • HEADER • PAYLOAD o n_filters o filter1 o filter2 o ... ODPSRP_HEADER DATA filter1 n_filters ... filter2 ... Figura 22
Ogni filtro è costituito da:
• name (nome del tipo di evento)
• operand (operando matematico del filtro {<,>,<=,>=,==,!=,>=<}) • value (valore del filtro)
• type (tipo di valore {INT,STRING}) • timestamp (tempo di inizio validità)
Ogni nodo inserisce all’interno del proprio JOIN REPLY tutti i filtri sottoscritti da Subscriber locali e tutti i filtri ancora validi ricevuti da altri nodi tramite JOIN REPLY (detti filtri di
forward).
I filtri sottoscritti da Subscriber locali avranno un timestamp pari all’istante di invio del JOIN REPLY, tutti gli altri invece manterranno il timestamp con il quale sono stati ricevuti.
All’interno di un JOIN REPLY viene inviato il subset minimo di filtri in modo da minimizzare l’overhead di comunicazione e di elaborazione; vediamo un esempio in Figura 23.
NODO PUBLISHER Publisher ODPSRP [X==-5] [X>0] NODO SUBSCRIBER Subscriber X>0 ODPSRP [X>0] JOIN REPLY [X>0] JOIN REPLY [X>0] [X==-5] NODO SUBSCRIBER Subscriber X>3 ODPSRP [X>3] NODO SUBSCRIBER Subscriber X==-5 ODPSRP [X==-5] [X>0] [X>3] JOIN REPLY [X>3] Figura 23
Ricordiamo che ogni filtro di forward scade dopo un tempo ODPSRP_FG_TIMEOUT; per ogni notifica ricevuta che risulta coperta da un filtro di forward, viene confrontato il campo timestamp del filtro di forward stesso con l’orologio di sistema: se dal confronto risulta che il filtro è scaduto, questo viene invalidato ed eliminato in quanto obsoleto.
I filtri sottoscritti localmente al contrario non scadono mai, ma vengono eliminati solo su ricezione di un’opportuna UNSUBSCRIBE dell’applicazione Subscriber che li ha generati. Da quanto detto pare necessaria la presenza di un meccanismo di sincronizzazione degli orologi di sistema dei vari nodi per garantire il corretto funzionamento del meccanismo di invalidazione dei filtri di forward. Tale meccanismo non è stato implementato all’interno del nostro sistema in quanto non necessario, dato che gli orologi di sistema di tutti i nodi sono perfettamente sincronizzati all’interno del simulatore Qualnet.
Osserviamo comunque che anche in una rete reale non ci sará bisogno di nessun meccanismo di sincronizzazione, ma sará sufficiente utilizzare dei tempi relativi inseriti all’interno del campo timestamp per specificare dal validitá di un dato filtro inviato ad un nodo vicino tramite un JOIN REPLY.
Ovviamente se un nodo non ha né sottoscrizioni locale né filtri di forward interessati agli advertisement contenuti in un JOIN QUERY, non invierà nessun JOIN REPLY.
Osserviamo che con il meccanismo descritto un nodo intermedio che riceve un filtro di forward diviene a tutti gli effetti un sottoscrittore egli stesso, infatti risponderá a tutti i successivi pacchetti JOIN QUERY contenenti advertisement di interesse fintanto che i filtri ricevuti rimangono validi, ovvero non sono ancora scaduti.
Questo a prima vista potrebbe essere un effetto indesiderato del sistema in quanto se ad un ciclo di costruzione della mesh di trasporto vengono attivati dei nodi lungo un cammino, questi rimangono attivi e si comportano come dei subscriber fintanto che il filtro precedentemente ricevuto non viene distrutto per vecchiaia, e tutto questo accade indipendentemente dal fatto che si trovino ancora su di un cammino utile verso il vero nodo Subscriber, attivando potenzialmente tutta una serie di nodi non effettivamente necessari al servizio di notifica e che potrebbero provocare una ridondanza di trasmissioni dannosa per l’efficienza ed efficacia del sistema.
Ciononostante abbiamo deciso di optare per questa soluzione in quanto garantisce una maggiore robustezza del sistema e una maggiore efficacia del servizio controbilanciata da un costo non esiguo in termini di efficienza; immaginiamo ad esempio cosa potrebbe accadere se un nodo Subscriber non riceve una JOIN QUERY ad un ciclo di ricostruzione della mesh, oppure se il suo JOIN REPLY non viene ricevuto da nessun: in questo caso la mobilitá dei nodi potrebbe aver reso il precedente path di forward del tutto incapace di operare il servizio di notifica; dando a tutti i nodi con filtri di forward ancora validi il potere di attivare dei propri cammini ad ogni ciclo di ricostruzione della mesh possiamo invece avere una maggiore probabilitá che il sistema riesca a continuare a servire il nodo Subscriber.
I pacchetti JOIN REPLY possono essere inviati in unicast o in broadcast a seconda del valore del parametro ODPSRP_REPLY_METHOD.
Per inviare tali pacchetti in broadcast è sufficiente inserire nel file di configurazione la seguente stringa:
ODPSRP_REPLY_METHOD BROADCASTt
Alternativamente si può utilizzare il meccanismo di invio di JOIN REPLY in unicast inserendo la stringa:
ODPSRP_REPLY_METHOD UNICAST
Nel caso non venga inserita nessuna delle due precedenti stringhe il sistema utilizzerá per default il metodo broadcast.
Quando operiamo in modalità unicast i pacchetti JOIN REPLY vengono inviati direttamente al NodeUp contenuto nella TABELLA DI FORWARD descritta nella precedente sezione [3.3.2].
Al contrario, quando operiamo in modalità broadcast i pacchetti JOIN REPLY vengono inviati con un indirizzo broadcast, quindi verranno recevuti da tutti i nodi nel raggio di copertura dell’antenna.
Di tutti questi nodi solo uno non deve scartare tale pacchetto, ovvero il NodeUp appena descritto, ovvero il nodo che si trova a monte lungo il path verso il nodo pubblicatore; per fare questo il nodo che invia il JOIN REPLY inserisce nell’header del pacchetto nel campo hopCount l’indirizzo del NodeUp.
Tutti i nodi che ricevono un pacchetto JOIN REPLY durante la modalità broadcast quindi controllano se il campo hopCount dell’header coincide con il proprio indirizzo: in caso affermativo processano il pacchetto, altrimenti lo scartano.
Il vantaggio di operare in modalità broadcast consiste nella maggiore velocità di risposta che il sistema sperimenta grazie alla possibilità di evitare di attraversare lo strato di routing che può introdurre ritardi e latenze; inoltre permette un risparmio di pacchetti grazie alla mancanza di messaggi di acknowledgement e all’utilizzo del meccanismo da noi denominato PASSIVE REPLY ACKNOWLEDGEMENT descritto in dettaglio nella sezione [3.3.7.5].
I pacchetti JOIN REPLY sono molto delicati per il protocollo e una loro mancata ricezione potrebbe causare una perdita di notifiche anche consistente: da qui la necessità di avere un meccanismo di acknowledgement che garantisca la corretta trasmissione e ricezione.
Particolarmente delicato è il problema di quando rispondere a un pacchetto JOIN QUERY con l’invio di un pacchetto JOIN REPLY: se ad esempio rispondiamo appena riceviamo un JOIN QUERY, i nodi vicini al nodo publisher risponderanno per primi; successivamente i nodi distanti 2 Hop invieranno il loro proprio JOIN REPLY; tale pacchetto dovrà essere ritrasmesso dai nodi distanti un solo Hop; a questo punto risponderanno i nodi distanti 3 hop e tali pacchetti andranno ritrasmessi dai nodi distanti 2 e 1 hop e così via…
Avremo quindi una grossa inefficienza dovuta a nodi distanti che faranno crescere esponenzialmente il numero di pacchetti JOIN REPLY trasmessi nell’intera rete.
La situazione rimane invariata se ogni nodo attende un intervallo fisso prima di inviare il proprio JOIN REPLY.
Per risolvere questo inconveniente propongo una mia personale soluzione dettagliata nella sezione [3.3.7.2].
[3.3.4] JOIN REPLY ACK
La mancata ricezione dei pacchetti JOIN REPLY può compromettere anche seriamente il buon funzionamento del servizio portando alla perdita di tutte le notifiche fino alla prossima costruzione della mesh dopo un intervallo pari a ODPSRP_QUERY_INTERVAL.
Per questo il protocollo prevede la possibilità di attivare un semplice meccanismo di acknowledgement e di timeout.
Attiviamo e configuriamo questo meccanismo tramite i seguenti parametri: • ODPSRP_UNICAST_REPLY_ACK
• ODPSRP_REPLY_ACK_TIMEOUT
• ODPSRP_MAX_REPLY_RETRASMISSION
ODPSRP_UNICAST_REPLY_ACK permette di attivare il meccanismo di acknowledgement tramite pacchetti unicast dedicati; nel file di configurazione della simulazione (“.config”) è sufficiente inserire la seguente stringa per attivare tale meccanismo:
ODPSRP_UNICAST_REPLY_ACK YES
ODPSRP_REPLY_ACK_TIMEOUT permette di configurare il timeout oltre il quale, senza la ricezione del relativo acknowledgement, un pacchetto JOIN REPLY è considerato non ricevuto ed è quindi ritrasmesso.
ODPSRP_MAX_REPLY_RETRASMISSION permette di indicare al protocollo il numero massimo di ritrasmissioni che un pacchetto JOIN REPLY può sperimentare prima di essere definitivamente scartato.
Un pacchetto di acknowledgement è costituito unicamente da un ODPSRP_HEADER: tale header in particolare è la copia precisa del pacchetto JOIN REPLY a cui si riferisce eccetto per il campo TYPE che contiene il carattere ‘A’ proprio per indicare che si tratta di un acknowledgement.
Tutti i pacchetti di acknowledgement sono inviati unicast al nodo che ha generato il JOIN REPLY corrispondente.
Nel caso si voglia disabilitare il meccanismo di acknowledgement tramite pacchetti unicast è sufficiente non inserire la precedente stringa nel file di configurazione della simulazione o alternativamente inserire la stringa:
Oltre al meccanismo appena descritto abbiamo implementato anche un secondo meccanismo che abbiamo denominato PASSIVE JOIN REPLY ACKNOWLEDGEMENT e che è descritto in dettaglio nella sezione [3.3.7.5].
[3.3.5] NOTIFICATION
I pacchetti NOTIFICATION sono così composti: • HEADER • PAYLOAD o n_notification o notification1 o notification2 o … ODPSRP_HEADER DATA notif1 n notification ... notif2 ... Figura 24
Sono quindi molto simili ai pacchetti JOIN QUERY ma al contrario di questi non contengono nessun advertisement.
I pacchetti NOTIFICATION vengono inviati in broadcast dal nodo pubblicatore ogni volta che questi riceve una notifica di un evento da un’applicazione Publisher locale soltanto nel caso in cui abbia ricevuto precedentemente un filtro tale da coprire l’evento stesso.
Da notare che un pacchetto NOTIFICATION può contenere più notifiche: questo per poter implementare in modo pulito il meccanismo denominato NOTIFICATION BUFFER dettagliato nella sezione [3.3.7.3].
Ogni nodo che riceve un pacchetto NOTIFICATION non duplicato controlla che le notifiche in esso contenute siano di interesse per qualche filtro locale: in caso affermativo invia le notifiche all’applicazione Subscriber che le ha sottoscritte.
Successivamente controlla se ha almeno un filtro di forward ancora valido relativo al nodo Publisher da cui ha ricevuto il pacchetto NOTIFICATION tale da coprire almeno una notifica in esso contenuta: in caso affermativo provvede a ritrasmettere in broadcast il pacchetto stesso, eliminando eventualmente tutte quelle notifiche che non sono coperte da nessun filtro di forward.
