Erwartungswert berechnen für ein Routing-Problem

Neue Frage »

depp56 Auf diesen Beitrag antworten »
Erwartungswert berechnen für ein Routing-Problem
Hallo,

ich habe hier folgende Aufgabe:

Sei R={r1,…,rn}R={r1,…,rn} mit n∈ℕn∈N eine Menge von Routern. Die Router sind untereinander voll vermascht, d. h. jeder Router hat eine direkt Verbindung zu allen anderen Routern. Darüber hinaus seien N={N1,…,Nk}N={N1,…,Nk} eine Menge von k∈ℕk∈N Nutzern. Jeder Nutzer hat direkte Verbindungen zu √n Routern, die zufällig gleichverteilt gewählt wurden.

Nutzer senden Pakete an andere Nutzer. Alle Pakete sind explizit an einen Nutzer addressiert; der Zielnutzer wird zufällig gleichverteilt unter allen Nutzern ausgewählt. Ein Router kann ein Paket direkt an einen Nutzer zustellen, wenn er eine direkte Verbindung zu dem Nutzer hat. Andernfalls muss der Router das Paket an einen anderen Router weiterleiten. Dieser Router wählt er zufällig gleichverteilt unter allen Routern aus und sendet ihm das Paket ("hot potato").

nun soll ich den Erwartungswert für die Anzahl der Sendevorgänge, bis ein Paket sein Ziel erreicht hat, berechnen.

Ich habe leider überhaupt keine Idee, wie ich vorgehen muss.

meine bisherigen Ideen:

P("Paket kann direkt zugestellt werden") = 1/(√/n)
P("hot potato") = 1/n
P("Paket erreicht sein Ziel") = P("Paket kann direkt zugestellt werden") + P("hot potato") = 1/(√/n) + 1/n

für den Erwartungswert müsste ich eine Wahrscheinlichkeit P(Anzahl Sendevorgänge) oder so ähnlich, irgendwie aufaddieren und ich schätze, die Summe sollte von 1 bis k laufen.

Ich hoffe, mir kann irgendjemand auf die Sprünge helfen.
Vielen Dank vorab!
depp56 Auf diesen Beitrag antworten »

ich sehe gerade, dass einige Zeichen nicht richtig übernommen wurden.
Im Dateianhang ist die Aufgabe, mit meinen bisherigen Ideen nochmal richtig aufgelistet
Huggy Auf diesen Beitrag antworten »

Es sei die Wahrscheinlichkeit, dass ein Router eine Nachricht zustellen kann. Damit eine Nachricht beim Sendevrgang zugestellt wird, musste sie vorher mal nicht zugestellt werden können. Sei die Zufallsgröße für die Nummer des Sendevorgangs der Zustellung. Dann hat man



Das ist die Zähldichte einer geometrischen Verteilung. Und von der sollst du den Erwartungswert bestimmen.

Anmerkung: Hier ist angenommen, dass der Router, wenn er nicht zustellen kann, die Nachricht eventuell auch zufällig an sich selbst sendet, was ein wenig unsinnig ist. Ansonsten wäre die Wahrscheinlichkeit, dass der nächste Router die Nachricht zustellen kann . Wenn die Zahl der Router groß ist, macht das allerdings keinen nennenswerten Unterschied.
depp56 Auf diesen Beitrag antworten »

Danke für die Antwort.

Laut Wikipedia wäre der Erwartungswert dann: , also /N) =

Stimmt das?
depp56 Auf diesen Beitrag antworten »

Hallo nochmal,

wegen p bin ich etwas am grübeln: die Nutzer haben ja direkte Verbindungen zu Routern. müsste es dann nicht: sein, sodass der Erwartungswert dann ist?
Huggy Auf diesen Beitrag antworten »

Zitat:
Original von depp56
wegen p bin ich etwas am grübeln: die Nutzer haben ja direkte Verbindungen zu Routern. müsste es dann nicht: sein,

Dann wäre . Kann das sein?

Zitat:
Laut Wikipedia wäre der Erwartungswert dann: , also /N) =

Richtig.
 
 
depp56 Auf diesen Beitrag antworten »

Hallo

Ich meinte für p natürlich Wurzel n / n. Also alle N durch n ersetzen, weil jeder Nutzer direkte Verbindungen zu Wurzel n Routern hat. Würde es so nicht eher stimmen?

Erinnerung: es gibt n Router und N Nutzer
HAL 9000 Auf diesen Beitrag antworten »

Zitat:
Original von depp56
Erinnerung: es gibt n Router und N Nutzer

Nein - wenn ich den Text richtig lese, gibt es Router sowie Nutzer. Wobei die Gesamtnutzerzahl gar keine Rolle spielt für diese Frage hier, denn es geht nur um die Kommunikation zwischen zwei dieser Nutzer.

kennzeichnet lediglich die Menge der Nutzer, d.h., ist gar keine Zahl.
depp56 Auf diesen Beitrag antworten »

Hm.. muss es bei der Lösung denn nun alles n oder N sein? Eigentlich hängt die Anzahl der Sendevorgänge doch von der Anzahl der Router ab, sodass in der Lösung alle N durch n ersetzt werden müssten, oder?
HAL 9000 Auf diesen Beitrag antworten »

Richtig, es hängt nur von ab.

------------------------------------------------------------------------------------

Exakte Rechnung im Rahmen des Modells: Offenbar ist eine Quadratzahl, sei also .

Ich gehe mal davon aus, dass der Nutzer keine Information hat, mit welchen anderen Nutzern seine Router verbunden sind, deswegen wählt er den Startrouter zufällig gleichverteilt aus den Möglichkeiten aus.

1) Mit Wahrscheinlichkeit kann der Router das Paket direkt zum Ziel leiten.

2) Mit Wahrscheinlichkeit hingegen leitet er das Paket zu einem anderen Router weiter. Da der anderer Router mit Wkt Kontakt zum Ziel hat, ist die Anzahl der in diesem Fall 2) nötigen Interrouter-Transfers geometrisch verteilt mit Erwartungswert .

Insgesamt sind das im Mittel



Sendevorgänge (die 2 kommen von den beiden Sendevorgängen vom ersten Nutzer zum Startrouter und vom letzten Router zum Zielnutzer).


Ist der Router so "dumm", auch Pakete an sich selbst zu schicken, dann ist das im Zähler durch zu ersetzen, es sind dann Sendevorgänge.
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »