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
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.
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.