SS08 Klausur
Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
Distanzvektor …
Es geht um folgende Klausur, Aufgabe 4, das Distanzvektor Routing.
Schritt 1 habe ich noch geschafft, aber bei Schritt 2 bekomm ich Probleme: In der Lösung steht als Distanz A-F 6 mit nexthop C. Warum?
Nach Schritt 1 hat A-D die Entfernung 3, D schickt A jetzt D-F mit Entfernung 2, folglich würde ich auf A-F = 5 mit nexthop D tippen. Was stimmt hier nicht in meinen Gedanken? Ich dachte zuerst, dass man die unterstrichenen Werte nicht benutzten darf, aber dann müsste Schritt 1 ja genauso aussehen wie die Starttabelle am Anfang (mit A-E und A-F unendlich), da hier ja alle Werte unterstrichen sind.
von a nach c ist d=1
von c nach f ist d=5
=>a nach f ist d=6
anderer weg ist
von a nach b ist d=7
von b nach f ist d=1
=>a nach f ist d=8
aber ist halt länger…
EDIT:das war 1.Schritt =)
Also ist es dann so gemeint, dass die Spalten 2-4 den Zustand von B,C,D widerspiegeln, nachdem die neuen Daten verschickt und die Tabellen angepasst wurden?
Darum muss ich also mit den Daten aus dem jeweils vorherigen Schritt rechnen?
die spalten 2-4 sind die aktuallisierten werte der distanztabelle von b,c,d (die unterstrichenen sind die aktuallisierten)
also im 1.schritt die initial werte
Wie komme ich dann eigentlich in Schritt 2 auf den Weg von A nach E mit 4,C ?
Da benutzt man doch die nebenstehenden Daten und nicht die vorherigen?
von a nach c ist d=1 (aus 1.schritt-tabelle)
von c nach e ist d=3 (aus 2.schritt-tabelle)
=>a nach e ist d=4
also in schritt 2 steht in den spalten 2-4 das drin was b,c,d nach dem 1.schritt in ihrer tabelle stehen haben
(diese werden ja nach dem ersten schritt simultan an a gesendet)
mit diesen und der tabelle von a aus dem 1. schritt wird dann im 2.schritt die tabelle von a aktuallisiert
Die Musterlösung ist imho wie mir gerade auffällt in sich inkonsistent.
Ich fang mal mit meiner Beweisführung an:
Aufgabenstellung. “In den folgenden Schritten senden B,C,D simultan ihre Distanztabellen an A. […] die vom Knoten A errechnete Distanztabelle nach Erhalt der Nachbarinformationen des jeweiligen Schritts stehen.”
Für mich bedeutet das ganz klar, dass die Tabelle auf der linken Seite an A geschickt wird und ALLE darin vorkommenden Informationen (unterstrichen heißt ja nur, dass sich diese Informationen VOR dem versenden an A geändert hat) in A verarbeitet werden.
Folglich sollte bei Schritt 2 die Entfernung A-F 5 mit Nexthop D sein.
Und jetzt kommt der Kracher: Du meintest, ich darf noch nicht die aktualisierten Werte nehmen.
Bei Schritt 2 die Entfernung A-E beträgt in der ML 4 mit nexthop C. Um dies berechnen zu können benötigt man aber die unterstrichene Entfernung C-E aus dem Vektor von C, die auch gerade erst aktualisiert wordne ist.
=> Bei der Berechnung von A-F und A-E wurde nicht konsistent gearbeitet. Also ist imo die Musterlösung falsch. Falls jemand nen Fehler in meinem Denken findet, immer her damit
jop seh ich auch so
und ich meinte man darf die aktuallisierten werte in der tabelle von a nicht im selben schritt verwenden
A-F bei Schritt 2 sollte Entfernung 5 haben, der Meinung bin ich auch - aber waere nexthop nicht C? Ich meine von A-D komme ich in 3 (nexthop C) und von D-F in 2, sollte doch C der nexthop sein oder nicht?
Edit: Oder hat das irgendwas mit dem oo durch Poisoned Reverse zu tun? Weil prinzipiell koennte man in Schritt 3 auch A-B mit D=6 und nh=C machen. Aus dem Skript werd ich nicht wirklich schlau was Poisoned Reverse betrifft…
Ich glaube du hast recht mit nexthop = C, ergibt sich, wenn man den Graphen auf der ersten Seite anschaut.
Die Aufgabe ist echt blöd gestellt (bei den anderen Aufgaben war der nexthop ja jeweils leicht ersichtlich).
Ja, nexthop = C komm ich jetzt auch. Hab mich da ursprünglich wohl mal verguckt, aber die meine grundsätzliche Argumentation von oben stimmt noch. Schließlich hat sich A-C und C-D ja nicht verändert (somit auch nicht A-D). Also müsste trotzdem 5 raus kommen. Schön, dass wir da jetzt alle einer Meinung sind 
Kommando zurueck, hab mir das nochmal naeher angeschaut.
Der Algorithmus verlangt ja, dass man einen Distanzvektor D_w bekommt, w ist in diesem Fall (im 2. Schritt) der Knoten D, der die veraenderte 2 enthaelt fuer F. Man sucht jetz aber min_w { c(u,w) + D_w(v) }. Also nimmt man die Kante von u=A nach w=D, was eine 4 ist, und D_w(v)=D_D(F) ist 2, demnach immer noch 6!
Glaube ich nicht. Es kommt zwar der Distanzvektor D_D bei A an mit D_D(F) = 2, aber c(u,w), also hier c(A, D) bezeichnet ja die bisher bei A billigste bekannte Verbindung zwischen A und D, nicht zwangsweise die direkte. Und die hat bereits bei Schritt 1 die Kosten 3.
also c(A, D) + D_D(F) = 3 + 2 = 5
Oder überseh ich mal wieder was?
Das waere zwar der bislang kuerzeste Pfad, aber c steht ja fuer eine Kante. Auf Uebung07 - Folie 2 steht auch: “diesmal wird für den 1. Teil statt eines Pfads eine Kante verwendet”. Daher denke ich, dass man auf jeden Fall mit der Kante rechnen muss, auch wenn es einen kuerzeren Pfad geben sollte. Der kuerzeste Pfad sollte waehrend der Iterationen schon irgendwann durchkommen hoffe ich 
Ok, das macht Sinn. Würde auch konsistent sein mit der Angabe der Datenstrukturen in dem Algorithmus. D.h. c(u,w) bezeichnet zwar tatsächlich die Kosten, nicht aber Pfadweise, sondern nur die eine Kante.
Hab das irgendwie einfach immer so als Gesamtkosten hingenommen.
Das würde bedeuten, dass ich immer nen Riesendenkfehler bei dem Algorithmus hatte, würde aber Sinn machen. Danke