(#29) Distanzvektor-Routing
Rolf Winter
https://www.youtube.com/watch?v=RrMkRuRXQko

Transkript (automatisch erstellt)

0:00 in diesem video wird das distanz vector routing genauer betrachtet eine klasse von routing verfahren bei denen im gegensatz zum links ruth inc ein
0:08 globales wissen erforderlich ist das heißt die router im netz müssen nicht jeden anderen router alle links und link kosten kennen
0:16 beim links verfahren hatten wir gesehen dass die router die informationen über ihre nachbarn und die link kosten zu ihren nachbarn an alle anderen router im
0:25 netz fluten müssen beim distanz vector routing ist dies nicht der fall router kommunizieren ausschließlich mit den direkt verbundenen nachbarn und mit
0:33 diesen wird der eigene sogenannte distanz vector ausgetauscht der distanz faktor ist dabei nur eine liste aller vom router erreichbaren ziele inklusive
0:42 der kosten vom router zu diesen zielen das heißt der distanz vector enthält keinerlei topologie informationen nur die distanz ist bekannt aber nicht wie
0:53 die router untereinander verbunden sind auch nicht welche rudolf sich auf welchen pfad befinden effektiv ist der distanz vector die eigene weiterleitung
1:01 tabelle um distanz vector routing einfache beschreiben zu können nutzen wir folgende notationen die funktion dx von z gibt die kosten des kürzesten
1:12 pfades von iks nachts zurück darüber hinaus gibt es eine kostenpunkt ioc die die kosten des links zwischen zwei direkt verbundenen knoten zurückgibt mit
1:24 diesen beiden funktionen kann man die balmont ford gleichung aufstellen die die grundlage der berechnung der kürzesten wege im router ist diese sagt
1:33 dass der kürzeste weg von einem router zu einem ziel im netz berechnet werden kann indem man für alle nachbarn die kosten zu diesen nachbarn plus die
1:44 kosten zum ultimativen ziel von diesem nachbarn aus als kosten für den gesamten pfad berechnet von diesen gesamtkosten über jeden nachbarn wählt man den
1:55 kürzesten weg trägt diesen in seinen eigenen distanz vector ein und teilt diesen neuen distanz vector all seinen nachbarn mit
2:03 hier ist ein beispiel dieses verfahrens neben wir c als ausgangs knoten und ge als zu berechnen das ziel c
2:13 hat drei nachbarn a b und d diese also a b und d teilen c mit wie weit der weg von ihnen zu ge ist in dem a b und d ihren distanz vector anziehen
2:28 übermitteln der weg von a nach b hat die kosten 5 von b nach c hat die kosten 3 und von d nachgeht hat die kosten 1 zu diesen
2:42 kosten muss zäh der ausgangs knoten nun die kosten zu diesen nachbarn addieren um die gesamtkosten zugeht zu ermitteln die kosten zudem sind zwei plus die
2:54 kosten von db sind insgesamt 3 die kosten von ccb sind eins plus die kosten von b zu gehen sind insgesamt vier die kosten von ca sind vier plus die kosten
3:09 von 5 für den part von acg ergibt 9 das heißt der kürzeste weg von cvg ist 3 über den nachbarn de damit welt c den weg über die und teilt dies wiederum
3:25 seinen nachbarn mit diese berechnet daraufhin ihren distanz vector neu wieder a nach b nach c finden dadurch eine bessere rote und damit
3:35 senden sie auch keinen aktualisierten distanz vektoren ihre nachbarn man sagt das routing hat konvergiert schauen wir uns diesen algorithmus noch
3:44 mal genauer an oder die direkt miteinander verbunden sind also direkte nachbarn sind tauschen ihre distanz vektoren miteinander aus
3:51 jeder router merkt sich die distanz vektoren der nachbarn basierend auf diesen distanz vektoren wird der eigene berechnet also die
4:00 eigenen kürzesten wege zu allen bekannten zielen im netz diese berechnung basiert wie eben gesehen ob der benford gleichung als input dienen
4:09 wie gesagt die distanz vektoren der nachbarn und die kosten zu diesen nachbarn sollte sich aufgrund dieser berechnung
4:15 der eigene distanz vector ändern dann wird dieser wiederum an die eigenen nachbarn verteilt die daraufhin ebenfalls beim import bemühen müssen um
4:22 zu überprüfen ob sich der eigene distanz weg dadurch geändert hat man sieht schon die routenfindung der distanz vector routing verfahren ist
4:30 interaktiv und es kann eine weile hin und her gehen bis das routing konvergiert das heißt die router keine weiteren updates des eigenen distanz
4:38 sektors schicken dieser algorithmus ist in der grafik dargestellt eine neuberechnung des eigenen distanz sektors wird durch ein
4:46 update eines nachbarn oder durch eine änderung der kosten zu einem nachbarn ausgelöst nur wenn sich dadurch ein neuer distanz
4:53 vector ergibt wird dieser mit den nachbarn geteilt was bei diesen eine neuberechnung auslöst und so weiter änderung der kosten entstehen übrigens
5:02 durch die konfiguration der router wir wollen uns ein kleines beispiel anschauen aber dazu muss zunächst ein wenig mutation eingeführt werden hier in
5:11 der abbildung ist ein kleines netz bestehend aus drei routen a b und c mitgegebenen link kosten alle router sind miteinander verbunden
5:20 das heißt direkte nachbarn und damit tauschen diese router distanz vektoren untereinander aus hier abgebildet ist eine tabelle aller gespeicherten distanz
5:28 vektoren bei mode a jede zeile der tabelle entspricht einem distanz vector von einem nachbarn beziehungsweise der eigene distanz
5:36 vector die ganz rechte spalte beinhaltet die kosten vom router zu den nachbarn hier im beispiel ist die unterste zeile der distanz vector von c man sieht die
5:47 distanz von zehn archa ist eins von zehn nach b ist viel und von 10-18 ist selbstverständlich 0 die kosten sind 1 das heißt nach berlin
5:58 fort muss jeder wert in der zeile noch mit 1 addiert werden um die kosten zu diesen zielen von aaraus zu berechnen die mittlere teile ist der distanz
6:07 vector von b und die oberste zeile ist der resultierende distanz vector von arm um diesen zu berechnen gehen wir spalten weise vor
6:15 die distanz von aaa ist 0 diese muss nicht berechnet werden die distanz von b ergibt das minimum aller distanzen der summe aus den kosten
6:25 zum nachbarn plus die kosten vom nachbarn zum ultimativen ziel berechnet über alle nachbarn gegeben durch die balmont ford gleichung das heißt die
6:36 kosten von b nach besen 0 bloss die kosten um zu b zu gelangen sind drei das heißt die gesamtkosten sind drei die distanz
6:45 von ccb ist 4 plus die kosten um zu ziel zu gelangen sind eins macht 5 damit ist der kürzeste weg von a nach b der direkte weg mit den kosten treiben
6:57 bleibt noch der weg von a nach c hier schauen wir in die letzte spalte die kosten von b nach c sind vier +3 um nach b zu gelangen sind 7
7:07 die kosten von 10 80 plus die kosten von 1 und nach b zu gelangen sind 1 insgesamt damit ist auch hier der direkte weg der
7:16 kürzeste und der distanz weg davon ist vollständig berechnet nehmen wir dieses beispiel und gehen davon aus dass zu beginn jeder router
7:25 nur die distanzen zu seinen eigenen nachbarn kennt und jeder router quasi synchron updates an seine nachbarn verschickt zum zeitpunkt null berechnen
7:33 alle router ihre distanz vektoren dann nur die kosten zu den eigenen nachbarn bekannt sind werden diese direkten roten gewählt und der eigene distanz vector
7:42 mit den nachbarn geteilt sprich schickt b und c sein distanz vector de schickt seinen an a und c und c seinen an a und b zum zeitpunkt 1 haben nun alle router
7:54 zwei neue distanz vektoren bekommen und berechnen den eigenen mit diesen neuen daten rosa findet aber keine besseren wege durch diese neuen daten b und c
8:04 aber schon eine kürzere route zu ca denn die kosten zu aasen 3 und a ha die kosten von eins zu zehn und das ist mit gesamtkosten von 4
8:16 günstiger als der direkte weg mit kosten 5 das heißt der distanz vector von b ändert sich das gleiche gilt für den distanz vector von c b und c teilen
8:27 diesen wieder all ihren nachbarn mit hingegen sendet kein update an b und c denn der distanz weg hat sich nicht geändert alle drei bekommen jedoch neue
8:37 informationen mit den updates und berechnen ihre distanz vektoren neu da es nun zu keinen änderungen der distanz vektoren kommt werden auch keine updates
8:46 verschickt das routing ist konvergiert bei distanz faktorverfahren propagieren sich günstigere wege und gefallene linken kosten schnell im netz
8:55 bei steigenden link kosten und ausfällen sieht dies aber ein wenig anders aus was wir am beispiel nachvollziehen wollen gehen wir davon aus dass in der
9:04 topologie rechts die link kosten zwischen a und b von 3 auf 50 steigen wir konzentrieren uns auf den nachrichtenaustausch zwischen a und c da
9:14 ein link von ah betroffen ist meta von der änderung zuerst basierend auf den neuen link kosten und den distanz vektoren der nachbarn wird der neue
9:23 distanz vector berechnet und zwar folgendermaßen die kosten von a nach b direkt sind auf 50 gestiegen aber der distanz vector von c sagt das c
9:33 ebenfalls b erreichen kann und zwar mit den kosten 4 noch eins addiert um von a nach b zu kommen ergibt gesamtkosten von 55 viel geringer ist als 50 wird nun den
9:47 weg nach b über zu wählen das problem ist dass cs weg zu b selbst überführt ncs distanz vector basiert auf altem
9:57 distanz vector distanz vector protokolle keinerlei detaillierte roten informationen austauschen sondern nur distanzen weiß dies aber nicht nachdem
10:07 nun einen neuen distanz vector berechnet hat wird dieser allen nachbarn mitgeteilt inklusive c&c berechnet seine distanz vector daraufhin neu und sieht
10:18 dass die kosten von a zu b gestiegen sind allerdings sind die kosten von 5 plus die kosten von 1 um nachzukommen immer noch geringer als die direkten
10:29 kosten von 40 das ergibt einen neuen distanz vector von c mit den kosten 6 zu den c wieder an seine nachbarn schickt inklusive
10:40 sieht den neuen distanz vector und berechnet seinen eigenen daraufhin neu und man sieht die kosten schauen sich langsam hoch bis sie irgendwann merkt
10:48 dass die kosten über den direkten link günstiger sind solange schicken sicher und sie allerdings sehr viele nachrichten und in
10:57 dieser zeit gibt es eine routing schleife danach schickt alle datenpakete für b an c&c schickt alle datenpakete von b
11:05 derart zurück dieses problem nennt man das count to end findet die probleme weil hier sehr lange die kosten eines pfades hoch gezählt werden
11:13 bis wieder der günstigste weg gefunden wird ein problem das den längst aid verfahren nicht vorkommt da die gesamte topologie jedem router bekannt ist für
11:23 das count to infinity problemen gibt es verschiedene lösungsansätze der erste wird pausen reverse genannt dabei geben router nicht immer ihren wahren distanz
11:32 vector bekannt sondern für alle routen die über einen bestimmten nachbarn gehen werden diese routen mit unendlichen kosten diesem nachbarn angegeben
11:41 damit soll sichergestellt werden dass dieser router sich bei steigenden kosten nicht für eine rote entscheidet dem countdown findet die problem endet
11:49 präsent reversed ist hier im beispiel abgebildet hat ein router c mitgeteilt bekommen dass eine route zu b über c und endlich gekostet da c selbst b über den
12:01 router erreicht kommt es jetzt zu kostenerhöhungen auf dem link zwischen roter und roter b dann berechnet seien distanz vector neu allerdings ist
12:11 diesmal 50 als die kosten des direkten weges viel günstiger als unendlich und wir damit gleich gewählt der neue distanz vector wird unter
12:20 anderem an c übermittelt welcher gleich seinen eigenen distanz vector neu berechnet sie wählt den direkten link zur b denn dieser hat die kosten 40
12:29 während die kosten über 51 wären auch c übermittelt einen neuen distanz vector und alle nachbarn und erfährt so über die neue route die zehn nutzt um b zu
12:40 erreichen die kosten von 40 für die strecke c nach a plus die kosten von 1 um nach c zu gelangen sind günstiger als die aktuelle
12:49 route mit kosten von 50 guter ändert damit seine distanz vector und verteilt diesen woraufhin sich allerdings keine roten meer ändern
12:58 dieses verfahren funktioniert allerdings nur garantiert in einfachen topologien anstatt kosten von unendlich zu ermitteln kann man auch den nachbarn die
13:07 routen nicht bekannt machen die über diesen nachbarn gehen dieses vorgehen nennt man split horizon bei der nachbar diese routen optionen damit nicht kennt
13:15 wird das count on findet die problem umgangen eine weitere möglichkeit besteht darin die routing information in den distanz
13:22 vektoren zu erweitern das bekannteste beispiel dafür ist das border gateway protocol kurz bip welches für das globale vernetzen der netzwerke
13:31 aus denen das internet aufgebaut ist verantwortlich ist anstelle einer einfachen metrik also den kosten die es zu minimieren gilt für bp den routen die
13:40 details der pfade hinzu damit kann jeder router direkt überprüfen ob es zu schleifen kommen kann nämlich immer dann wenn der router schon teil des pfades
13:49 ist dann muss diese route verworfen werden in wickie wird allerdings keine router informationen preisgegeben sondern nur
13:56 die liste der netzwerke die dieser route durchläuft das heißt es wird eine sehr limitierte sicht auf die route preisgegeben
14:04 man weiß dadurch welche netze zum beispiel miteinander verbunden sind aber kennt nur informationen über pfade die eine mitgeteilt werden und kennt
14:12 keinerlei details über den inneren aufbau der netze die metrik die es zu minimieren gilt ist somit die pfad länge also die anzahl der netze die einfahrt
14:21 durchläuft wenn man ganz genau ist hat man damit kein reines distanz vector protokoll mehr aber die preisgabe dieser limitierten fahrt informationen erlaubt
14:30 es schleifen zu vermeiden im letzten video haben wir links date verfahren kennen gelernt diese wollen wir nun mit distanz vector verfahren
14:38 vergleichen frühling state verfahren haben wir festgestellt dass globales wissen benötigt wird das heißt alle router links und kosten dieser links
14:47 müssen jede mutter bekannt sein das macht das fluten dieser information notwendig aber diese vollständige topologie kenntnis macht link state
14:54 verfahren robust und in grenzen deterministisch was die konvergenz zeit betrifft diese verfahren werden in den netzen der einzelnen provider benutzt
15:03 aber nicht zwischen verschiedenen providern distanz vector verfahren fluten keine informationen sondern tauschen diese nur mit direkten nachbarn
15:10 aus das verfahren ist dadurch interaktiv dann neue informationen an nachbar verteilt werden die daraufhin wieder einen neuen distanz weg bilden was
15:18 wiederum zur änderung führen kann und so weiter das heißt die konvergenz zeit kann stark variieren auch sind temporäre routing schleifen
15:26 möglich wenn keine geeigneten gegenmaßnahmen eingesetzt werden distanz vectoring wird in leicht abgewandelter form als pfad vector
15:34 protokoll zwischen den netzen der netzbetreiber eingesetzt dieses protokoll heißt bgp selten werden distanz vector protokolle auch im campus
15:42 netzen eingesetzt allerdings werden hier links date verfahren aufgrund ihrer positiven konvergenz eigenschaften bevorzugt zusammenfassend distanz vector
15:51 protokolle arbeiten mit dezentraler informationen oder verteilter informationen den router können die topologie nicht sondern arbeiten mit
15:58 informationen die sie von nachbarn erhalten die aber keinerlei topologie informationen enthalten sondern eine einfache kosten metrik route berechnen
16:07 die günstigsten fahrer anhand der einfachen bällen ford leitung diese vorgehensweise hat gewisse vorteile wie zum beispiel das fluten von
16:15 informationen nicht nötig ist außerdem verstecken diese routing protokolle den inneren aufbau der netze das sehen viele netzbetreiber als
16:22 entscheidenden vorteil denn diesen möchte man eventuell nicht anderen netzbetreibern offenlegen der nachteil von distanz vector
16:29 protokollen ist das konvergenz zeiten stark variieren können da das verfahren interaktiv ist und es je nach utting änderungen
16:36 unterschiedlich lange dauern kann bis alle router wieder die kürzesten wege gefunden haben auch gibt es das kaum drin findet die
16:42 problem dass distanz faktorverfahren inhärent erzeugen können auch können viele informationen die an router in das netz schickt katastrophale folgen haben
16:50 da die anderen router keine detaillierte topologie information haben um eventuelle fehlinformationen besser behandeln zu können
16:58 einige dieser probleme lassen sich mit bekannten mechanismen lösen andere sind interent durch das fehlen von detaillierten topologie informationen