Frage zu Kürzeste-Wege-Problem in Graphen

[Alexander H. (ill_son)]

Hallo,

ich hatte neulich schon mal eine Frage zu Graphen und da habe ich sehr 
gute Hilfe erhalten, deshalb versuche ich es nochmal hier.

Ich habe eigentlich nur eine Grundsatzfrage zum oben genannten Problem:

Funktionieren die gängigen Verfahren, wie Dijkstra oder Bellmann-Ford 
oder auch nur eine einfache Breitensuche in Graphen, dessen Topologoie 
global nicht bekannt ist, wo also jeder Knoten nur seine Nachbarn kennt? 
Die ganzen Verfahren verwenden ja eine globale Warteschlange. Ich habe 
neulich bei meiner Recherche auf eine Uni-Seite gelesen, dass z.B. die 
Breitensuche ohne globale Sicht auf den Graphen nicht funktioniert. Wie 
läuft das in Netzwerken beim Erstellen der Routingtabellen, da weiß doch 
auch nicht jeder Router über alle anderen Router bescheid, oder doch?

Grüße, Alex

[Max M. (jens2001)]

http://de.wikipedia.org/wiki/Border_Gateway_Protocol

[Alexander H. (ill_son)]

Hallo Max,

vielen Dank. Da steht allerdings, dass es sich an 
Distanzverktorprotokollen orientiert.

http://de.wikipedia.org/wiki/Border_Gateway_Protocol#Besonderheiten_bei_BGP

Und da bin ich wieder bei Bellman-Ford, bzw. bei der Breitensuche auf 
die sich Bellmann-Ford bei gleichen Kantengewichten reduzieren lässt. 
Funktioniert die ohne globale Sicht? Offensichtlich ja schon. Ich habe 
noch gelesen, dass man auch eine beschränkte Tiefensuche statt dessen 
durchführen kann, dies aber eher bei Problem mach, bei denne der Graph 
so groß ist, dass der Speicherplatz nicht reicht.

[Max M. (jens2001)]

Die topologische Struktur des I-Net ist kein engmaschiges Netz sondern 
entspricht eher einer hierarchischen Baumstruktur mit wenigen 
Querverbindungen. So gibt es zwischen großen Netzbetreibern nur wenige 
Übergangspunkte (z.B. http://de.wikipedia.org/wiki/DE-CIX).
Ausserdem ist das Inet nach IP-Adressbereichen organisiert. So braucht 
ein Router nicht die ganze Route kennen sondern nur die Route in das 
Netz in dem sich der  Zielknote befindet.