HomePage .:.   Forum .:.

P2P Sicuro

P2P Classico

eMule Plus

Shareaza

GrabIt

P2P Download

Software P2P

MUTE. MUTE, istradamento messaggi e....formiche

Le formiche mostrano di avere un' 'intelligenza collettiva' quando cercano il cibo o combattono contro un predatore. Ogni formica della colonia si comporta in un modo molto semplice ma prese tutte insieme riescono a fare cose molto intelligenti, come scoprire il percorso più breve che separa il formicaio e una fonte di cibo. Il meccanismo di istradamento messaggi di MUTE è ispirato al comportamento delle formiche.

Molte specie di formiche comunicano con i loro compagni usando delle 'fragranze' chimiche conosciute come ferormoni. I ferormoni possono essere usati in diversi modi dalle formiche e da altri animali ( compresi gli umani ) ma noi siamo soprattutto interessati a come le formiche usano i ferormoni per orientarsi l'una con l'altra nel loro ambiente -- questo problema è strettamente collegato al problema di direzionare il flusso di informazioni in una rete.

Consideriamo una colonia di formiche che cerca cibo. Osservando una colonia di formiche si ha l'impressione che le formiche si muovano in linea retta tra il loro formicaio e la fonte di cibo. Camminare in linea retta, che spesso significa compiere il percorso più breve, sembra essere una soluzione ovvia al problema di un trasporto efficiente di cibo.

Ovviamente noi umani faremmo la stessa cosa, infatti marciamo spesso in linea retta sia quando viaggiamo in gruppo sia quando viaggiamo soli. Ora nonostante noi abbiamo cervelli immensi paragonati a quelli delle formiche, con un sistema visivo straordinariamente complicato ( il 25% del cervello umano è dedicato alla visione ) e nonostante riusciamo ad avere una visione più globale del terreno potendo guardare da più in alto non riusciamo a trovare il percorso 'più breve tra due punti' in un ambiente complicato e pieno di ostacoli in modo così efficiente e veloce come lo troverebbe una colonia di formiche usando la sua  intelligenza collettiva. Ma allora ci chiediamo : come fanno?

Supponiamo che una colonia di formiche non abbia inizialmente nessuna informazione circa la posizione del cibo. La strategia umana in questo caso sarebbe quella di organizzare una 'spedizione di ricerca' per ispezionare l'area circostante - lo scout che trova il cibo ne riporta un poco a casa ed informa gli altri circa la posizione del cibo. Anche le formiche cercano il cibo camminando in maniera casuale che è una cosa simile al meccanismo umano di esplorazione, ma due problemi impediscono alle formiche di implementare una spedizione di ricerca simile a quella umana.

Il primo è : come può una formica-esploratrice , alla scoperta del cibo, trovare da sola la strada per tornare al nido? IL secondo problema è : anche se l'esploratrice facesse ritorno a casa  come potrebbe informare le altre  circa la posizione del cibo? La risposta sta nell'uso intelligente dei ferormoni.

Per risolvere il problema di trovare la casa ogni formica lascia una traccia di ferormone quando cerca il cibo. Nella seguente foto di esempio la traccia di ferormone lasciata da ogni formica in perlustrazione è mostrata in rosso trasparente:

Quando una formica trova cibo, può seguire la traccia del suo stesso ferormone per tornare al formicaio - questo è molto simile a lasciare delle bricioline di pane attraverso la foresta per ritrovare la strada di casa.  Tornata a casa la formica risolve il problema di 'dire alle altre che ha trovato cibo'  rilasciando una dose più consistente di ferormone e creando una traccia con un odore più forte. Nella seguente immagine, la formica A raggiunge il cibo per prima e quindi segue la sua traccia verso casa, mentre le altre tre formiche continuano ad esplorare.

Quando le altre formiche si imbattano in una scia di ferormoni terminano la loro ricerca casuale ed iniziano a seguire la scia. Nell'immagine seguente , la formica D scopre la doppia traccia lasciata dalla formica A e comincia a seguirla. La formica C incontra la singola traccia lasciata dalla formica D e comincia a seguire quella traccia, che la condurrà eventualmente alla traccia di A. La formica B invece supponiamo che scopra di proprio conto il cammino che porta al cibo , cammino che è completamente diverso da quello scoperto da A.

Se una traccia di ferormone conduce una formica di nuovo a casa a bocca asciutta, questa si gira e segue la scia nella direzione opposta a quella da cui è venuta. Una volta che una formica raggiunge il cibo ne afferra un pezzetto e torna indietro seguendo la stessa scia verso casa. Sulla strada di ritorno la formica rinforza la scia lasciando molto ferormone. Nella seguente immagine la formica C si unisce alla formica A ma la segue nella direzione sbagliata, raggiungendo il formicaio a bocca asciutta. La formica B segue la sua traccia indietro fino al formicaio -- non è mai venuta a contatto con la traccia più diretta che le altre formiche stanno usando. A e D portano indietro del cibo al fomicaio e consolidano il percorso.

Abbiamo spiegato come le formiche trovano il cibo, ma come fanno a scegliere il percorso più breve verso il cibo? Un ulteriore dettaglio ci aiuta a rispondere a questa domanda: le formiche preferiscono seguire le tracce dove è più forte l'odore del ferormone. Percorsi più brevi tra il formicaio e il cibo vengono completati in tempi minori e quindi percorsi più volte. Questo renderà i percorsi più brevi anche più 'odorosi' di ferormone. La seguente immagine dimostra questo punto. Quando B deposita cibo presso il formicaio e si prepara a partire per un altro viaggetto sente l'odore del percorso usato dalle altre formiche e abbandona il suo percorso . A questo punto tutte e quattro le formiche usano il percorso scoperto dalla formica A per trasportare cibo.

Col passare del tempo ( e supponendo com'è normale che siano migliaia e migliaia le formiche iniziali ) vengono esplorati moltissimi percorsi ma l'odore del percorso più breve viene rinforzato più frequentemente degli altri percorsi, così questo diventa anche il percorso più popolare e presto tutte le formiche lo percorreranno per trasportare il cibo.

Semplici regole

L'approccio delle formiche nel trovare i percorsi più vantaggiosi è molto diverso da quello con cui gli umani si muovono nel loro ambiente. Noi studiamo visivamente il territorio cercando di trarne una visione globale e cerchiamo di pianificare mentalmente un percorso più breve. Naturalmente il metodo delle formiche ha dei vantaggi rispetto al nostro approccio di 'alto livello'. Per esempio il metodo delle formiche funziona perfettamente anche nella più completa oscurità. Invece quando gli umani si devono orientare senza l'ausilio visivo riescono a fare ben poco.

Il metodo della formica può essere schematizzato in semplici regole che vengono seguite da ogni membro della colonia:

Semplificare la natura

Sebbene la tabella delle 'regole semplici' sopra sia relativamente facile da capire contiene ancora delle regole che non sono così semplici come potremmo pensare. Inoltre c'è un comportamento sub-ottimo da considerare: ad esempio una formica potrebbe seguire una traccia di ferormone nella direzione sbagliata, ovvero nella direzione verso casa. Ovviamente quando una formica senza cibo raggiunge il formicaio si gira e torna sui suoi passi verso il cibo ma questo è comunque un comportamento che fa perdere tempo. Il problema sembra essere la mancanza di direzione nella traccia di ferormone, ed è certo difficile rappresentare la direzione quando tutto ciò con cui devi lavorare sono delle sostanze chimiche odorose.

Nel mondo della programmazione di rete, non siamo limitati come i percorsi di ferormoni privi di direzione. Aggiungendo una direzione a tali percorsi siamo in gradi di estrapolare un insieme di regole più semplici.

Supponiamo di aver a che fare con formiche con due tipi di ferormone invece che di uno, e supponiamo di dare a questi ferormoni il significato di direzione. Il primo ferormone potrebbe essere pensato come se dicesse " da questa parte si va a casa" e lo chiameremo un ferormone 'trova-casa'. il secondo ferormone sarà il ferormone 'trova-cibo' e punta nella direzione del cibo. Quando le formiche lasciano il formicaio in cerca di cibo camminano in maniera casuale  lasciando tracce di ferormone trova-casa mentre procedono. Quando una formica trova cibo ne prende un pezzettino e segue la sua traccia di ferormone  trova-casa verso il formicaio, lasciando una traccia di ferormone trova cibo. Se una formica vagante incontra una traccia trova-cibo la segue fino a raggiungere il cibo,lasciando mentre procede più ferormone trova-casa.

Questa semplice modifica riduce la complessità dell'insieme di regole:

Disegnare frecce nella foresta

Questo meccanismo è simile al mondo in cui gli umani si muovono in una foresta disegnando frecce colorate sui tronchi degli alberi. Per esempio le frecce blu potrebbero significare "strada verso il lago" , mentre le frecce gialle potrebbero significare "strada verso casa". Se ti allontani da casa in cerca del lago, puoi disegnare frecce gialle rivolte all'indietro mentre procedi. Al ritorno dal lago puoi seguire le frecce gialle verso casa mentre disegni frecce blue indietro verso il lago. La cosa importante qui è che tu sai sempre come tornare al punto da cui sei venuto , sebbene potresti non riuscire ad arrivare dive stai cercando di andare. Se ti imbatti in un albero che ha già una freccia disegnata vi aggiungi semplicemente la tua freccia anche se è la stessa che è già disegnata.

Dopo che molte persone sono andare dalla casetta al lago usando questo metodo, ci saranno molte frecce disegnate attraverso la foresta --- molti alberi saranno segnati con molteplici frecce anche indicanti diverse contraddittorie direzioni. Quando cerchi di trovare la strada per casa come interpreterai una albero con 10 frecce gialle? Ci sono molte possibili strategie, ma la più semplice potrebbe essere di seguire la direzione indicata dalla maggior parte delle frecce, poiché probabilmente indicano il percorso più breve ( ricorda che i percorsi più brevi sono anche i più veloci così gestiscono più traffico ).

Come MUTE instrada i messaggi

In una rete non abbiamo formiche che cercano cibo o boy scout che cercano di trovare il percorso tra la casa ed il lago. Abbiamo invece messaggii che devono viaggiare da un mittente ed un destinatario. Poiché gli utenti di MUTE sono anonimi nessuno dei nodi sulla rete sa esattamente dove trovare un destinatario particolare ( o più precisamente quale computer un particolare destinatario sta usando ). Come le formiche che sono ignare dell'intero sistema , i messaggi di MUTE devono essere diretti attraverso la rete usando solo sussidi locali.

Ogni nodo di MUTE mantiene connessioni con diversi vicini nella rete , e queste connessioni con i vicini vengono usate per scambiarsi messaggi. Supponiamo che il nodo X di MUTE riceva un messaggio da Alice verso Bob attraverso il nodo Y, uno dei suoi vicini. X può non avere la più pallida idea di dove Bob si trovi sulla rete. Tuttavia , ricevendo questo messaggio il nodo X apprende qualcosa riguardo ad Alice: ovvero apprende che i messaggi di Alice gli sono arrivati  dal nodo Y. In futuro se il nodo X riceve un messaggio verso Alice, usando questa regola invierà il messaggio direttamente al nodo Y.

Trascurando ciò che X apprende di Alice, non ha comunque informazioni riguardo Bob. La migliore strategia qui, ispirandoci alle formiche, è di inviare 'le formiche in tutte le direzioni' o di mandare una copia del messaggio ad ognuno dei vicini di X. Se nessuno dei vicini di X ha informazioni di dove sia Bob allora tutti fanno come ha fatto X ovvero trasmetteranno a tutti i loro rispettivi vicini una copia del messaggio. Se Bob esiste sulla rete con questa tecnica verrà alla fine trovato.

Nota che durante la ricerca di Bob, il messaggio ha lasciato una traccia di indizi ed informazioni circa Alice. Se il messaggio raggiunge Bob e quindi Bob invia indietro una risposta , la risposta può seguire questi indizi su un percorso più diretto verso Alice.

Mentre la risposta viene instradata verso Alice, essa lascia una traccia di indizi che possono essere usati per instradare futuri messaggi da Alice a Bob. Anche gli altri nodi possono usare questi indizi, ad esempio se il proprietario del nodo X invia un messaggio a Bob, il messaggio viaggerà seguendo un percorso piuttosto diretto usando gli indizi esistenti.

Guardando questi diagrammi di esempio possiamo comprendere che il meccanismo di istradamento di MUTE è molto simile alla tecnica di 'Disegnare frecce nella foresta'  presentata prima. Ogni nodo può essere pensato come un albero, ed ogni connessione vicina può essere pensata come un percorso tra alberi adiacenti. Ogni nodo mantiene una collezione di frecce  ed ogni freccia indica qualcosa del tipo 'Per raggiungere Bob usa questo percorso'. In questi diagrammi noi seguiamo la freccia blue a ritroso per trovare Bob.

Possiamo anche pensare come se ciascun messaggio lasciasse un 'odore' mentre viaggia attraverso la rete. I messaggi di alice lasciano 'l'odore di Alice' e possiamo seguire questa scia quando inviamo messaggi ad Alice. Le frecce più scure in questo  diagramma rappresentano il messaggio , mentre le frecce trasparenti possono essere pensate come se fossero la traccia lasciata.

Indizi di istradamento e privacy

In termini di anonimato la nozione di 'indizi su Alice' sembrerebbe turbarci. Ricordiamo però che tutti questi ' indizi ' sono solamente suggerimenti locali che non danno la possibilità a nessuno di individuare direttamente Alice sulla rete. Un indizio di istradamento su Alice essenzialmente ti dice :" il mio vicino ne sa su Alice più di me". Naturalmente nessuno dei nodi può capire quante informazioni ha su Alice così il fatto che un particolare vicino ne sappia di più su Alice vuol dire che tale nodo ha solo poche informazioni in più. Nessuno dei nodi lungo il percorso tra Alice e Bob avrà abbastanza informazioni per concludere 'il mio vicino è Alice'

^Top^