Einfachen Routing-Algorithmus implementieren
Routing-Algorithmus
Der vorgeschlagene Algorithmus kommt ohne die Angabe eines Zielortes aus. Es wird ausschließlich die Zielperson benötigt.
Sicht auf die Daten
Wir benötigen dafür folgende Sicht auf die Daten für einen gegebenen Zeitraum (beispielsweise 30 Tage):
Person: alice@instanz Datum + evtl. Uhrzeit: von/bis Ort: Kartenpunkt Umkreis: in km geschätzt?: ja/nein
Die Daten sollten dabei für den Zeitraum vollständig, konsistent und lückenlos sein. Dazu können wir folgende Annahmen treffen:
- Wenn wir über den Aufenthaltsort einer Person nichts wissen, dann befindet sie sich an ihrem Heimatort (geschätzt: ja).
- Für die übrigen Orte können wir entsprechend der Häufigkeitsangaben („bin alle zwei Wochen für zwei Tage dort“) und des letzten Aufenthalts bzw. des letzten geschätzten Aufenthalts den Aufenthaltsort abschätzen (geschätzt: ja).
- Angaben, die die Person konkret selbst gemacht hat, werden mit „geschätzt: nein“ angegeben.
Idee als Ergänzung (nicht im Prototyp): Orte auf Reisewegen (Zwischenstationen, Umsteigebahnhöfe, …) können mit in die Sicht aufgenommen werden.
Der Umkreis hat einen Default-Wert (pro Person änderbar) und kann auch für jeden Ort/ jeden Aufenthalt gesetzt werden.
Föderation
Die Sicht gibt uns erste Hinweise auf ein mögliches Protokoll für die Föderation. Jede Instanz muss bei anderen Instanzen diese Sicht auf die Daten abfragen können.
Das Routing sollte vermutlich immer von der Instanz der Zielperson berechnet werden, diese hat das Interesse, dass die Sendung ankommt. Die Instanz der Startinstanz gibt also nur einen Auftrag (mit aktuellem Status der Sendung) an die Instanz der Zielperson und damit die Verantwortung ab.
Nicht im Prototyp: Die Identitäten der Personen in der Liste sollten später verschleiert werden. Beispielsweise kann auf jede Anfrage mit einer Zahl geantwortet werden und die Identitäten können nur im Zusammenhang mit dieser Zahl und nur von der Instanz selbst zugeordnet werden. Mit einem Routing-Auftrag wird dann die Identität des Senders in der verschleierten Liste markiert übergeben.
Erreichbarkeits-Graph
Dieser Graph kann statisch berechnet werden und jeweils bei Abruf von neuen Listen aktualisiert werden. Alternativ kann er auch dynamisch vom Startknoten aus schrittweise berechnet werden (s.u.).
Sei G = (V, E) ein Graph. V ist die Menge der Knoten und umfasst die Personen. E ist die Menge der Kanten. Für jedes Paar von Knoten (v1, v2) mit v1 und v2 aus V füge E eine Kante hinzu, wenn sich v1 und v2 in einem Zeitraum am selben Ort befinden (unter Berücksichtigung des Umkreises). Annotiere die Kante mit dem Zeitraum. Annotiere außerdem die Angabe „geschätzt“, wenn mindestens eine der beiden beteiligten Ortsangaben als „geschätzt“ markiert ist.
Route berechnen
Annotiere den Startknoten mit dem Zeitpunkt des Auftrags. Ausgehend vom Startknoten berechne für jeden umliegenden Knoten (verbunden durch eine Kante) den Zeitpunkt der frühestmöglichen Übergabe (unter Berücksichtigung des an der Kante annotierten Zeitraums). Annotiere den Zeitpunkt am Knoten. Das Kantengewicht berechnet sich jeweils aus der Differenz der Knotenzeitpunkte.
Auf dieser Grundlage kann eine Route als „Kürzester Weg“ (bspw. mit dem Dijkstra-Algorithmus) berechnet werden.
Zustellbarkeit
Solange auf der berechneten Route Kanten mit der Angabe „geschätzt“ liegen, müssen die Ortsangaben bei den Personen angefragt und aktualisiert werden. Anschließend muss die Route neu berechnet werden.
Eine Route, auf der keine Kanten mehr mit „geschätzt“ annotiert sind, gilt als zustellbar.
Wenn der Algorithmus keine Route mit endlicher Entfernung findet, ist die Sendung innerhalb des Zeitraums (bspw. 30 Tage) unzustellbar. Es können mehr Nutzer:innen geworben und mehr Informationen über Reisen gesammelt werden. Anschließend kann der Algorithmus erneut nach einer Route suchen.
Nicht im Prototyp: Es wäre möglich, Sendungen bei Nicht-Zustellbarkeit zumindest räumlich „näher“ an den Heimatort der Zielperson heranzubefördern. Dazu können ausgehend vom Heimatort Orte gesucht werden, deren Distanz zum Ziel näher ist und an denen sich möglichst viele Personen häufig aufhalten. Gibt es eine Route zu so einem Ort, kann die Sendung zunächst dorthin befördert werden und anschließend erneut nach Routen gesucht werden.