Routenplanung ist der Prozess, Pfade in einem Netz auszuwählen, entlang dem man Netzverkehr sendet. Routenplanung wird für viele Arten von Netzen, einschließlich des Telefonnetzes (Leitungsvermittlung), elektronische Datennetze (wie das Internet) und Transport-Netze durchgeführt. Dieser Artikel wird in erster Linie mit der Routenplanung in elektronischen Datennetzen mit der Paket-Schaltungstechnologie betroffen.

In Paket-Schaltungsnetzen leitet Routenplanung Paket-Versand, die Durchfahrt logisch gerichteter Pakete von ihrer Quelle zu ihrem äußersten Bestimmungsort durch Zwischenknoten, normalerweise Hardware-Geräte genannt Router, Brücken, Tore, Brandmauern oder Schalter. Mehrzweckcomputer können auch Pakete nachschicken und Routenplanung durchführen, obwohl sie nicht spezialisierte Hardware sind und unter der beschränkten Leistung leiden können. Der Routenplanungsprozess leitet gewöhnlich Versand auf der Grundlage von Routenplanungstischen, die eine Aufzeichnung der Wege zu verschiedenen Netzbestimmungsörtern aufrechterhalten. So ist das Konstruieren von Routenplanungstischen, die im Gedächtnis des Routers gehalten werden, für die effiziente Routenplanung sehr wichtig. Die meisten Routenplanungsalgorithmen verwenden nur einen Netzpfad auf einmal, aber Mehrpfad-Routenplanungstechniken ermöglichen den Gebrauch von vielfachen alternativen Pfaden.

Routenplanung, in mehr engerem Sinn des Begriffes, wird häufig mit dem Überbrücken in seiner Annahme gegenübergestellt, dass Netzadressen strukturiert werden, und dass ähnliche Adressen Nähe innerhalb des Netzes einbeziehen. Weil strukturierte Adressen einem einzelnen Routenplanungstabellenzugang erlauben, den Weg zu einer Gruppe von Geräten zu vertreten, überbietet das strukturierte Wenden (Routenplanung, im engeren Sinn) das unstrukturierte Wenden (Überbrücken) in großen Netzen, und ist die dominierende Form des Wendens im Internet geworden, obwohl Überbrücken noch innerhalb von lokalisierten Umgebungen weit verwendet wird.

Liefersemantik

Routenplanungsschemas unterscheiden sich in ihrer Liefersemantik:

• unicast liefert eine Nachricht an einen einzelnen spezifischen Knoten;
• Sendung liefert eine Nachricht an alle Knoten im Netz;
• Mehrwurf liefert eine Nachricht an eine Gruppe von Knoten, die Interesse am Empfang der Nachricht ausgedrückt haben;
• anycast liefert eine Nachricht irgend jemandem aus einer Gruppe von Knoten, normalerweise ein nächster zur Quelle.
• geocast liefert eine Nachricht an ein geografisches Gebiet

Unicast ist die dominierende Form der Nachrichtenübergabe im Internet, und dieser Artikel konzentriert sich auf unicast Routenplanungsalgorithmen.

Topologie-Vertrieb

In einer Praxis, die als statische Routenplanung (oder nichtanpassungsfähige Routenplanung) bekannt ist, können kleine Netze manuell konfigurierte Routenplanungstische verwenden. Größere Netze haben komplizierte Topologien, die sich schnell ändern können, den manuellen Aufbau von Routenplanungstischen unausführbar machend. Dennoch verwendet der grösste Teil des Publikums hat Telefonnetz geschaltet (PSTN) vorgeschätzte Routenplanungstische mit Rückgriff-Wegen, wenn der direkteste Weg blockiert wird (sieh Routenplanung im PSTN). Anpassungsfähige Routenplanung oder dynamische Routenplanung, versucht, dieses Problem zu beheben, indem sie Routenplanungstische automatisch, gestützt auf der Information gebaut wird, die durch Routenplanungsprotokolle getragen ist, und dem Netz erlaubend, fast autonom im Vermeiden von Netzmisserfolgen und Verstopfungen zu handeln.

Beispiele von Algorithmen der anpassungsfähigen Routenplanung sind Routing Information Protocol (RIP) und der Offene Kürzeste Pfad das Erste Protokoll (OSPF). Anpassungsfähige Routenplanung beherrscht das Internet. Jedoch verlangt die Konfiguration der Routenplanungsprotokolle häufig eine Fachberührung; Netzwerkanschluss der Technologie hat sich zum Punkt der ganzen Automation der Routenplanung nicht entwickelt.

Entfernungsvektor-Algorithmen

Entfernungsvektor-Algorithmen verwenden den Algorithmus von Ford des Öffentlichen Ausrufers. Diese Annäherung teilt eine Zahl, die Kosten zu jeder der Verbindungen zwischen jedem Knoten im Netz zu. Knoten werden Information vom Punkt senden, um B über den Pfad anzuspitzen, der auf die niedrigsten Gesamtkosten (d. h. die Summe der Kosten der Verbindungen zwischen den Knoten verwendet) hinausläuft.

Der Algorithmus funktioniert auf eine sehr einfache Weise. Wenn ein Knoten zuerst anfängt, weiß er nur von seinen unmittelbaren Nachbarn und den direkten Kosten, die am Erreichen von ihnen beteiligt sind. (Diese Information, die Liste von Bestimmungsörtern, den Gesamtkosten zu jedem, und dem folgenden Sprung, um Daten zu senden, um hierher zu kommen, setzen den Routenplanungstisch oder Entfernungstisch zusammen.) Sendet jeder Knoten regelmäßig an jeden Nachbar seine eigene aktuelle Idee von den Gesamtkosten, zu allen Bestimmungsörtern zu kommen, von denen es weiß. Der benachbarte Knoten untersucht diese Information, und vergleicht sie damit, was sie bereits 'wissen'; irgendetwas, was eine Verbesserung darauf vertritt, was sie bereits haben, fügen sie in ihren eigenen Routenplanungstisch (E) ein. Mit der Zeit werden alle Knoten im Netz den besten folgenden Sprung für alle Bestimmungsörter und die besten Gesamtkosten entdecken.

Wenn einer der beteiligten Knoten hinuntergeht, verwerfen jene Knoten, die ihn als ihr folgender Sprung für bestimmte Bestimmungsörter verwendet haben, jene Einträge, und schaffen neue Routenplanungstisch-Information. Sie passieren dann diese Information zu allen angrenzenden Knoten, die dann den Prozess wiederholen. Schließlich erhalten alle Knoten im Netz die aktualisierte Information, und werden dann neue Pfade zu allen Bestimmungsörtern entdecken, die sie noch "erreichen" können.

Mit der Verbindung staatliche Algorithmen

er mit der Verbindung staatliche Algorithmen anwendet, verwendet jeder Knoten als seine grundsätzlichen Daten eine Karte des Netzes in der Form eines Graphen. Um das zu erzeugen, überschwemmt jeder Knoten das komplette Netz mit der Information darüber, wozu anderen Knoten es in Verbindung stehen kann, und jeder Knoten dann unabhängig diese Information in eine Karte sammelt. Mit dieser Karte bestimmt jeder Router dann unabhängig den am wenigsten gekosteten Pfad von sich bis jeden anderen Knoten mit einem kürzesten Standardpfad-Algorithmus wie der Algorithmus von Dijkstra. Das Ergebnis ist ein Baum, der am aktuellen solchem Knoten eingewurzelt ist, dass der Pfad durch den Baum von der Wurzel bis jeden anderen Knoten der am wenigsten gekostete Pfad zu diesem Knoten ist. Dieser Baum dient dann, um den Routenplanungstisch zu bauen, der den besten folgenden Sprung angibt, um vom aktuellen Knoten bis jeden anderen Knoten zu kommen.

Optimierter Verbindungsstaatsroutenplanungsalgorithmus

Ein mit der Verbindung staatlicher Routenplanungsalgorithmus, der für das Mobiltelefon ad hoc Netze optimiert ist, ist das Optimierte Verbindungsstaatsroutenplanungsprotokoll (OLSR). OLSR ist proaktiv; es verwendet Hallo und Nachrichten von Topology Control (TC), um Verbindungszustandinformation unter dem Mobiltelefon ad hoc Netz zu entdecken und zu verbreiten. Mit Hallo Nachrichten entdeckt jeder Knoten 2-Sprünge-Nachbarinformation und wählt eine Reihe von Mehrpunktrelais (MPRs). MPRs unterscheiden OLSR aus anderen Verbindungszustandroutenplanungsprotokollen.

Pfad-Vektor-Protokoll

Entfernungsvektor und Verbindungszustandroutenplanung sind beide Intrabereichsroutenplanungsprotokolle. Sie werden innerhalb eines autonomen Systems, aber nicht zwischen autonomen Systemen verwendet. Beide dieser Routenplanungsprotokolle werden unnachgiebig in großen Netzen und können in der Zwischenbereichsroutenplanung nicht verwendet werden. Entfernungsvektor-Routenplanung ist der Instabilität unterworfen, wenn es mehr gibt als einige Sprünge im Gebiet. Verbindungszustandroutenplanung braucht riesigen Betrag von Mitteln, Routenplanungstische zu berechnen. Es schafft auch Lastenverkehr wegen der Überschwemmung.

Pfad-Vektor-Routenplanung wird für die Zwischenbereichsroutenplanung verwendet. Es ist der Entfernungsvektor-Routenplanung ähnlich. In der Pfad-Vektor-Routenplanung nehmen wir an, dass es einen Knoten gibt (es kann viele geben) in jedem autonomen System, das im Auftrag des kompletten autonomen Systems handelt. Dieser Knoten wird den Sprecher-Knoten genannt. Der Sprecher-Knoten schafft einen Routenplanungstisch und kündigt ihn benachbarten Sprecher-Knoten in benachbarten autonomen Systemen an. Die Idee ist dasselbe als Entfernungsvektor-Routenplanung, außer dass nur Sprecher-Knoten in jedem autonomen System mit einander kommunizieren können. Der Sprecher-Knoten kündigt den Pfad, nicht die metrischen von den Knoten, in seinem autonomen System oder anderen autonomen Systemen an.

Pfad-Vektor-Routenplanung wird RFC 1322 besprochen; der Pfad-Vektor-Routenplanungsalgorithmus ist dem Entfernungsvektor-Algorithmus im Sinn etwas ähnlich, dass jeder Grenzrouter die Bestimmungsörter ankündigt, die es zu seinem benachbarten Router erreichen kann. Jedoch, statt Werbenetze in Bezug auf einen Bestimmungsort und die Entfernung zu diesem Bestimmungsort, werden Netze als Bestimmungsort-Adressen und Pfad-Beschreibungen angekündigt, um jene Bestimmungsörter zu erreichen. Ein Weg wird als eine Paarung zwischen einem Bestimmungsort und den Attributen des Pfads zu diesem Bestimmungsort, so der Name, die Pfad-Vektor-Routenplanung definiert, wo die Router einen Vektoren erhalten, der Pfade zu einer Reihe von Bestimmungsörtern enthält.

Der Pfad, der in Bezug auf die Gebiete (oder Bündnisse) ausgedrückt ist, überquert bis jetzt, wird in einem speziellen Pfad-Attribut getragen, das die Folge von Routenplanungsgebieten registriert, durch die die reachability Information gegangen ist.

Vergleich von Routenplanungsalgorithmen

Entfernungsvektor-Routenplanungsprotokolle sind einfach und in kleinen Netzen effizient und verlangen wenig, falls etwa, Management. Jedoch haben traditionelle Entfernungsvektor-Algorithmen schlechte Konvergenz-Eigenschaften wegen des Problems der Zählung zur Unendlichkeit.

Das hat zur Entwicklung von komplizierteren, aber mehr ersteigbaren Algorithmen für den Gebrauch in großen Netzen geführt. Innenroutenplanung verwendet größtenteils mit der Verbindung staatliche Routenplanungsprotokolle wie OSPF und IST - IST.

Eine neuere Entwicklung ist die von Entfernungsvektor-Protokollen ohne Schleifen (z.B, EIGRP). Entfernungsvektor-Protokolle ohne Schleifen sind so robust und lenksam wie naive Entfernungsvektor-Protokolle, aber vermeiden, bis Unendlichkeit zu zählen, und haben gute Grenzfall-Konvergenz-Zeiten.

Pfad-Auswahl

Pfad-Auswahl ist mit Verwendung einer zu vielfachen Wegen metrischen Routenplanung verbunden, um auszuwählen (oder vorauszusagen) der beste Weg.

Im Fall vom Computernetzwerkanschluss wird das metrische durch einen Routenplanungsalgorithmus geschätzt, und kann solche Information wie Bandbreite, Netzverzögerung, Sprung-Zählung, Pfad-Kosten, Last, MTU, Zuverlässigkeit und Nachrichtenkosten bedecken (sieh z.B diesen Überblick für eine Liste der vorgeschlagenen Routenplanungsmetrik). Der Routenplanungstisch versorgt nur die bestmöglichen Wege, während mit der Verbindung staatliche oder topologische Datenbanken ganze andere Information ebenso versorgen können.

Weil eine metrische Routenplanung zu einem gegebenen Routenplanungsprotokoll spezifisch ist, müssen Mehrprotokoll-Router einige äußerlich heuristisch verwenden, um zwischen von verschiedenen Routenplanungsprotokollen erfahrenen Wegen auszuwählen. Die Router von Cisco schreiben zum Beispiel einen Wert zu, der als die Verwaltungsentfernung zu jedem Weg bekannt ist, wo kleinere Verwaltungsentfernungen von einem vermutlich zuverlässigeren Protokoll erfahrene Wege anzeigen.

Ein lokaler Netzverwalter, in speziellen Fällen, kann mit dem Gastgeber spezifische Wege zu einer besonderen Maschine aufstellen, die mehr Kontrolle über den Netzgebrauch, Erlaubnisse zur Verfügung stellt zu prüfen und bessere gesamte Sicherheit. Das kann handlich nach Bedarf eingehen, um bei Netzverbindungen oder Routenplanungstischen die Fehler zu beseitigen.

Vielfache Agenten

In einigen Netzen wird Routenplanung durch die Tatsache kompliziert, dass keine einzelne Person dafür verantwortlich ist, Pfade auszuwählen: Statt dessen werden vielfache Entitäten am Auswählen von Pfaden oder sogar Teilen eines einzelnen Pfads beteiligt. Komplikationen oder Wirkungslosigkeit können resultieren, wenn diese Entitäten Pfade wählen, um ihre eigenen Ziele zu optimieren, die die Ziele anderer Teilnehmer kollidieren können.

Ein klassisches Beispiel schließt Verkehr in einem Straßensystem ein, in dem jeder Fahrer einen Pfad aufpickt, der ihre eigene Fahrzeit minimiert. Mit solcher Routenplanung können die Gleichgewicht-Wege länger sein als optimal für alle Fahrer. Insbesondere Braess Paradox zeigt, dass das Hinzufügen einer neuen Straße Fahrzeiten für alle Fahrer verlängern kann.

In einem anderen Modell, das zum Beispiel für die Routenplanung verwendet ist, hat geführte Fahrzeuge (AGVs) auf einem Terminal automatisiert, Bedenken werden für jedes Fahrzeug gemacht, gleichzeitigen Gebrauch desselben Teils einer Infrastruktur zu verhindern. Diese Annäherung wird auch des Zusammenhangs bewusste Routenplanung genannt.

Das Internet wird in autonome Systeme (ESEL) wie Internetdienstleister (ISPs) verteilt, von denen jeder Kontrolle über Wege hat, die sein Netz an vielfachen Niveaus einschließen. Erstens werden WEIL-NIVEAU-Pfade über das BGP Protokoll ausgewählt, das eine Folge des ESELS erzeugt, durch den Pakete fließen werden. Jeder, WIE vielfache Pfade haben kann, die durch das Grenzen an ESEL angeboten sind, von dem man wählt. Seine Entscheidung ist häufig mit Geschäftsbeziehungen mit diesen verbunden, an ESEL grenzend, der zur Pfad-Qualität oder Latenz ohne Beziehung sein kann. Zweitens, sobald ein WEIL-NIVEAU-Pfad ausgewählt worden ist, gibt es häufig vielfache entsprechende Pfade des Router-Niveaus teilweise, weil zwei ISPs in vielfachen Positionen verbunden werden können. In der Auswahl des einzelnen Pfads des Router-Niveaus ist es übliche Praxis für jeden ISP, um Heiß-Kartoffelroutenplanung zu verwenden: Das Senden des Verkehrs entlang dem Pfad, der die Entfernung durch das eigene Netz des ISP minimiert — selbst wenn dieser Pfad die Gesamtentfernung zum Bestimmungsort verlängert.

Denken Sie zwei ISPs, A und B, der jeder eine Anwesenheit in New York hat, das durch eine schnelle Verbindung mit der Latenz 5 Millisekunden verbunden ist; und der jeder eine Anwesenheit in durch eine Verbindung der 5 Millisekunde verbundenem London hat. Nehmen Sie beide an, welche ISPs transatlantische Verbindungen haben, die ihre zwei Netze verbinden, aber Eine Verbindung hat Latenz, haben 100 Millisekunden und B Latenz 120 Millisekunden. Wenn Routenplanung eine Nachricht von einer Quelle in Einem Londoner Netz zu einem Bestimmungsort im B New Yorker Netz, A beschließen kann, die Nachricht an B in London sofort zu senden. Das spart die Arbeit des Sendens davon entlang einer teuren transatlantischen Verbindung, aber veranlasst die Nachricht, Latenz 125 Millisekunden zu erfahren, als der andere Weg 20 Millisekunden schneller gewesen wäre.

Eine 2003-Maß-Studie von Internetwegen hat gefunden, dass, zwischen Paaren, an ISPs zu grenzen, mehr als 30 % von Pfaden Latenz wegen der Heiß-Kartoffelroutenplanung mit 5 % von Pfaden aufgeblasen haben, die durch die Inflation von mindestens 12 Millisekunde wegen der WEIL-NIVEAU-Pfad-Auswahl, während wesentlich, verzögern werden, wurde in erster Linie dem Mangel von BGP an einem Mechanismus zugeschrieben, für die Latenz, aber nicht zu egoistischen Routenplanungspolicen direkt zu optimieren. Es wurde auch darauf hingewiesen, dass, ein passender Mechanismus im Platz waren, würde ISPs bereit sein zusammenzuarbeiten, um Latenz zu reduzieren aber nicht Heiß-Kartoffelroutenplanung zu verwenden.

Solch ein Mechanismus wurde später von denselben Autoren zuerst für den Fall von zwei ISPs und dann für den globalen Fall veröffentlicht.

Weg-Analytik

Da das Internet und die IP Netze Mission kritische Geschäftswerkzeuge werden, dort ist Interesse an Techniken und Methoden vergrößert worden, die Routenplanungshaltung von Netzen zu kontrollieren. Falsche Routenplanung oder Routenplanungsprobleme verursachen unerwünschte Leistungsdegradierung, das Flattern und/oder Ausfallzeit. Die Überwachung der Routenplanung in einem Netz wird mit Weg-Analytik-Werkzeugen und Techniken erreicht.

Siehe auch

Routenplanungsalgorithmen und Techniken

• beerdigen Sie Bereichsroutenplanungsalgorithmus
• Intra-Bereichsroutenplanungsalgorithmus
• Anpassungsfähige Routenplanung
• Routenplanung des alternativen Pfads
• Ablenkungsroutenplanung
• Rand zusammenhangloser kürzester Paar-Algorithmus
• Der Algorithmus von Dijkstra
• Krause Routenplanung
• Geografische Routenplanung
• Heuristische Routenplanung
• Hierarchische Routenplanung
• IP Versand des Algorithmus
• Mehrpfad-Routenplanung
• Bedeckungsnetzroutenplanungsschemas
• Schlüsselbasierte Routenplanung (KBR)
• Dezentralisierte Gegenstand-Position und Routenplanung (DOLR)
• Gruppe anycast und Mehrwurf (WERFEN)
• Verteilte Hash-Tabelle (DHT)
• Pfad-Berechnungselement (PCE)
• Politikbasierte Routenplanung
• Qualität des Dienstes in der Routenplanung
• Statische Routenplanung
• Rückwärts das Lernen der Routenplanung

Routenplanung in spezifischen Netzen

• Weg-Anweisung in Transport-Netzen
• Nationaler Routeing-Führer: Personenroutenplanung im Schiene-Netz des Vereinigten Königreichs
• Routenplanung im PSTN
• Kleine Weltroutenplanung - das Internet ist ungefähr ein kleine Weltnetz

Routenplanungsprotokolle

• Routenplanungsprotokoll
• Klassenlose Zwischenbereichsroutenplanung (CIDR)
• MPLS Routenplanung
• ATM Routenplanung
• RPSL
• RSMLT
• Routenplanung in optischen Ineinandergreifen-Netzen

Alternative Methoden für den Netzdatenfluss

• Gleicher-zu-Gleicher-
• Netz, das codiert

Router-Software und Gefolge

• GNU-Zebra
• Quagga (Software)
• Iproute2

Router-Plattformen

• Netz Betriebssystem - NO
• XORP - die ausziehbare Offene Router-Plattform
• Junos
• Cisco ein/Ausgabe-Steuersystem
• NX-OS
• CatOS

Links

• Graf zur Unendlichkeit Problem
• "Stabilitätseigenschaften" sind Weisen, die "Zählung zur Unendlichkeit" Problem zu vermeiden.
• Cisco ES Fallstudien über die Routenplanung und umschaltend
• gutes Beispiel an der Ereignis-Spirale