Come faccio a scegliere il percorso di routing migliore? Devo sapere chi sia il destinatario e posso usare una conoscenza locale della rete per scegliere il prossimo vicino a cui inoltrare il messaggio.
Devo avere anche id distinti altrimenti potrei avere destinatari doppi.
Possiamo andare a considerare un costo particolare per archi/percorsi, anche perché devo capire dove mandarlo in maniera più conveniente. Idealmente vorrei prendere il percorso di costo minore.
Ci interessa studiare quanto spazio devo allocare localmente per tenere le informazioni per fare routing. L’ideale sarebbe farsi una tabella di routing per un nodo s e questo mi costa nlogw (dove w sono altri identificativi univoci). Come search time stiamo su logn praticamente.
Potrei andare a considerare il cammino minimo perché ha una sotto struttura ottima, quindi se da uno shortest path vado a prendere un nodo random, anche quello è potenzialmente un cammino minimo. In questo io localmente posso ricordarmi solamente il prossimo link più breve che devo fare così alla fine tutti insieme ci ricordiamo il percorso più breve.
Quali possono essere le idee per costruire queste tabelle?
Map_Gossip
Potremmo fare gossiping in cui tutti fanno broadcast, all to all. Così lo scopo finale è che fondamentalmente se s avesse il grafo e si costruisse uno spanning tree giusto, che è quello di avere un albero di cammini minimi che mi vado a calcolare con Dijkstra. Deve sapere a chi, i nodi vicini, possono arrivare. Se s conoscesse l’albero dei cammini minimi potrebbe farsi la tabella.
Devo fare per forza fare un broadcast della coppia di dati: vicini-costo, da tutti quanti i nodi essenzialmente così il nodo di partenza arriva ad avere una conoscenza del grafo. Devo mettere insieme delle informazioni, ma ci si riesce!
Quindi: gossip_map → dijkstra → tabella routing
Per prima cosa dobbiamo però andare a fare uno spanning tree e visto che abbiamo gli ID univoci dovremmo fare una leader election perché ci conviene andare a fare un broadcast efficiente. Quindi per fare broadcast efficiente ci serve un leader, che sfrutti lo spanning tree che abbiamo creato prima della leader election. Quindi: spanning tree - leader election - broadcast.
Mi costa alla fine come la somma di tutti i gradi dei nodi di ogni grafo, perché sarebbe messaggi * archi per ogni nodo, che alla fine equivale alla cosa che dicevo prima.
I broadcast li vado a fare sullo spanning tree. Considerando che mandiamo un identificativo alla volta su ogni messaggio, quanti sono i messaggi da far girare un nodo col suo broadcast? Il numero di vicini per il suo grado? N - 1 link (perché siamo nello spanning tree).
Per un broadcast pago: (n-1)deg(x)
Per tutti quanti i broadcast: $\sum_{x}((n-1)deg(x)=(n-1)\sum_{x}=(n-1)*2m$
Per fare la routing table non ho bisogno di altri messaggi.
Come message complexity come siamo messi?
O(mn)
Tutti quanti i nodi devono avere spazio per tenersi in memoria la loro mappa di routing.