DE102004031717A1

DE102004031717A1 - Effiziente Berechnung von Routingtabellen für ein Routing anhand von Zieladressen

Info

Publication number: DE102004031717A1
Application number: DE102004031717A
Authority: DE
Inventors: Joachim Dr. Charzinski; Thomas Engel; Christoph Reichert
Original assignee: Siemens Corp
Current assignee: Nokia Solutions and Networks GmbH and Co KG
Priority date: 2004-06-30
Filing date: 2004-06-30
Publication date: 2006-01-26
Also published as: US20100329154A1; EP1762060A1; CN1998196A; WO2006003141A1

Abstract

Die Erfindung betrifft ein Verfahren und eine Vorrichtung (NCS) für ein verteiltes Berechnen von Routingtabellen für ein Routing in einem mit Knoten (A, ..., G) und Links gebildeten Kommunikationsnetz. Die Berechnung der zu verwendenden Routen wird zentral vorgenommen. Informationen bzgl. der zu verwendenden Routen werden an einen Knoten (D) kommuniziert, welcher auf Grund dieser Informationen eine Routingtabelle (FIB) durch Zuordnung von Paketadressen zu den Routen berechnet. DOLLAR A Die zentrale Berechnung der Routen führt zu einer erhöhten Ressourceneffizienz bzgl. des Rechenaufwandes. Diese Aufwandsreduktion macht sich besonders in Netzen mit Mehrwegerouting bemerkbar, in denen die Berechnung von Routingtabellen (FIB) besonders aufwändig ist und zudem noch eine weitere Reduzierung des Aufwands durch zentrale Berechnung der Verteilungsgewichte erfolgen kann.

Description

Die Erfindung betrifft ein Verfahren und eine Vorrichtung zur Berechnung einer Routingtabellen für ein Routing innerhalb eines mit Knoten und Links gebildeten Kommunikationsnetzes.
Der Transport von Verkehr in Datennetzen, vor allem im Hinblick auf Einhaltung von Dienstgüteparametern, ist ein aktuelles Arbeitsgebiet für Netzwerkspezialisten und Internetfachleute.

Der Großteil heutiger Datennetze ist mit Knoten bzw. Routern und Links bzw. Kanten gebildet, wobei der Verkehr paketweise von Knoten zu Knoten übermittelt wird. Üblicherweise bestimmt sich der nächste Knoten (oder der "next hop") aus der dem Knoten vorliegenden Routingtabelle, welche die in den Paketen enthaltenen Zieladressen mit nächsten Hops in Beziehung setzt. Üblicherweise werden die Routingtabellen mittels Routingprotokollen aufgestellt bzw. berechnet. Beispiele für derartige Routingprotokolle sind das OSPF (Open Shortest Path First)-Protokoll, welches in dem Internet verwendet wird und zusammen mit dem IP (Internet Protocol)-Protokoll eingesetzt wird, sowie das IS/IS (Intermediate System to Intermediate System)-Protokoll. Das Routing anhand von in den Paketen spezifizierten Zieladressen wird auch als "Destination Based Routing" oder Routing anhand von Zieladressen bezeichnet.

Herkömmliches Routing in Datennetzen ist ein "Best Effort"-Routing, das heißt, es werden keine Garantien für die Dienstgüte beziehungsweise die Einhaltung von Dienstgüteparametern gegeben. Neue Entwicklungen gehen dahin, das Routingkonzept von Datenpaketen für die Übertragung von Echtzeitdaten, wie Sprache, Video- oder Audioinformationen zu erweitern, wozu es der Einhaltung von Dienstgüteparametern bedarf. Ein zentraler Ansatz für die Verbesserung der Übertragungsqualität bei Datenübertragung über ein Datennetz ist die Verwendung von Mehrwegerouting, d.h. zu einem Ziel werden alternative Routen zur Verfügung gestellt, wodurch der Ausfall von Links oder Überlastsituationen abgefangen werden können.

Der Aufwand bei der Berechnung von Routingtabellen nimmt mit der Zunahme möglicher Ziele und vor allem – bei Mehrwegerouting – möglicher Routen erheblich zu.

Die Erfindung hat zur Aufgabe, die Berechnung von Routingtabellen für mit Knoten und Links gebildete Kommunikationsnetze zu optimieren.

Die Aufgabe wird durch die Gegenstände der unabhängigen Ansprüche 1 und 10 gelöst. Die Erfindung beruht auf dem Gedanken, einen Teil der Berechnungen für die Aufstellung von Routingtabellen auf einem Server durchzuführen. Im folgenden wird vereinfacht von einem Server ausgegangen und werden seine Berechnungen zentrale Berechnungen genannt, obwohl zur Verbesserung der Verfügbarkeit auch ein Verbund mehrerer Server genutzt werden kann. Erfindungsgemäß wird eine zentrale Berechnung von Routen zwischen jeweils einem netzinternen Anfangs- und Endknoten vorgenommen. Dabei ist netzintern so zu verstehen, dass Anfangs- und Endknoten Knoten des Netzes sind, das heißt, Randknoten oder innere Knoten. Für Verkehr, welcher zu einem Ziel außerhalb des Kommunikationsnetzes geleitet wird, ist es sinnvoll, als Endknoten einen der Randknoten des Kommunikationsnetzes zu verwenden, von dem der Verkehr in Richtung Ziel in ein anderes Netz übertragen wird. Informationen über die zentral berechneten Routen werden – beispielsweise mittels eines Kommunikationsprotokolls – einem Knoten des Netzes mitgeteilt. Diese Informationen bestehen z.B. aus der Angabe des nächsten Hops für das Routing zu einem Randknoten.

Auf Grundlage dieser Informationen berechnet der Knoten mittels eines Routingprotokolls, zum Beispiel dem OSPF-Protokoll oder dem IS/IS-Protokoll, die Einträge für eine Routingtabelle. Dabei werden über das Routingprotokoll gelernte Zieladressen von zu transportierenden Paketen den zentral berechneten netzinternen Routen zugeordnet. Diese Zuordnung kann anhand von eindeutigen Router-IDs erfolgen, zum Beispiel anhand der im OSPF Standard RFC2328 beschrieben 32-Bit Router-ID. Die an den Router übermittelten Informationen müssen nicht notwendigerweise vollständige Routen beinhalten. Im Prinzip können die Informationen über die berechneten Routen auf die Informationen beschränkt werden, die für eine Zuordnung von Zieladressen zu Routen notwendig ist. Wie umfangreich die Informationen im Einzelfall sind, hängt von dem verwendeten Routing ab. Bei herkömmlichen IP Netzen können z.B. die nächsten Hops für das Routing zu einem Endknoten innerhalb des Netzes (z.B. einem Randknoten, von dem aus ein Weiterrouten in ein anderes Netz erfolgt) und der jeweilige Endknoten spezifiziert werden.

Die Erfindung hat den Vorteil, dass die Berechnung der Routen zentral erfolgt und so die die Routen betreffenden Informationen einer Vielzahl von Knoten, zum Beispiel allen Knoten des Netzes, weitergegeben werden können, so dass der entsprechende Rechenaufwand nur einmal und nicht für alle die Routen verwendenden Knoten anfällt. Die Erfindung ist besonders vorteilhaft bei der Verwendung von Mehrwegerouting, weil in diesem Fall die Routenberechnung deutlich aufwändiger ist und so mehr Rechenaufwand eingespart werden kann. Informationen, die nur zur Routenberechnung verwendet werden, beispielsweise eine Verkehrsmatrix, braucht so nicht an die einzelnen Knoten verteilt zu werden. Bei Mehrwegerouting kann zudem eine zentrale Bestimmung von Verkehrsverteilgewichten vorgenommen werden Verkehrsverteilgewichte dienen zur Steuerung der Aufteilung des Verkehrs auf die alternativen Routen des Mehrwegeroutings und können am Router für die Bestimmung bzw. Berechnung von Routingtabellen verwendet werden. Trotz der zentralen Berechnungen kann bei Mehrwegerouting jeder Knoten im Fehlerfall weiterhin selbständig reagieren, dass heißt Ver kehr von einer ausgefallenen Verbindung zu einem Nachbarknoten auf die verbleibenden Routen des Mehrwegeroutings umleiten, ist also nicht auf eine schnelle Reaktion der zentralen Berechnungen angewiesen.

Die Erfindung umfasst auch eine Vorrichtung zur Berechnung einer Routingtabelle innerhalb eines mit Knoten und Links gebildeten Kommunikationsnetzes, welche eine zentrale Vorrichtung (z.B. ein Server) mit Mitteln zur Berechnung von Routen zwischen Endknoten eines Netzes, sowie wenigstens einen Knoten mit Mitteln zum Erstellen einer Routingtabelle mittels eines Routingprotokolls umfasst. Dabei sind Mittel zur Kommunikation zwischen der zentralen Vorrichtung und dem beziehungsweise den Knoten gegeben, welche zum Beispiel ein Kommunikationsprotokoll umfassen. Falls das Netz mit Mehrwegerouting arbeitet, können auch Mittel zur Bestimmung von Verkehrsverteilgewichten in der zentralen Vorrichtung und Mittel zur Übermittlung der Verteilungsgewichte zu den Knoten gegeben sein.

Im Folgenden wird der Erfindungsgegenstand im Rahmen eines Ausführungsbeispiels anhand einer Figur näher erläutert.
In der Figur ist eine zentrale Vorrichtung NCS (NCS: steht für Network Control Server) dargestellt, welche erfindungsgemäß einen Teil der Berechnungen für die Erstellung von Routingtabellen vornimmt. Weiter sind Router bzw. Knoten A bis G gezeigt, welche Teil eines Netzwerks bilden. Anhand der Figur wird beschrieben, wie der Router D einen Teil seiner Routingtabelle mit Hilfe von durch die zentrale Vorrichtung NCS bereitgestellter Routinginformationen berechnet. Die Router A, F, G und E stellen nächste Hops bzw. unmittelbar dem Router D verbundene Knoten dar. Die Router B und C sind Randrouter des Netzes, über welche Verkehr zu anderen Netzen weitergeleitet wird. Die punktierten Verbindungen, mit denen diese beiden Randrouter B und C mit den anderen dargestellten Routern des Netzes verbunden sind, deuten ausgelassene Netzelemente (Rou ter und Links) an, über welche Verkehr zu den Randknoten weitergeleitet werden kann. In der Tabelle T1 ist Information enthalten, welche von der zentralen Vorrichtung NCS dem Knoten D übermittelt wird. Diese Information ist bestimmt für ein Mehrwegerouting, welches für die Übertragung von Verkehr zu einem Ziel wenigstens zwei alternative nächste Hops von D vorsieht. Durch die zentrale Vorrichtung wird dem Knoten vorgegeben, dass zu dem Randknoten B zu übermittelnder Verkehr zu 20% über den nächsten Hop F und zu 80% über den nächsten Hop G zu übertragen sind. Verkehr zu dem Randknoten C soll zu 60% über den nächsten Hop E und zu 40% über den nächsten Hop G übertragen werden. In der Tabelle T2 sind Adressen P1 bis P3 von Netzwerken dargestellt, welche über den Randrouter bzw. Randknoten C erreichbar sind. In entsprechender Weise sind in der Tabelle T3 die Adressen P4 bis P6 von Netzwerken dargestellt, welche über den Randrouter B erreichbar sind. Die Darstellung der Adressen folgt der üblichen Konvention für die Darstellung von IP-Adressen, wobei die Adresse und die für die Interpretation der Adresse als Netzwerkadresse notwendige Maske (hinter dem Schrägstrich) angegeben ist. Mittels des OSPF-Protokolls werden die Informationen über die über jeweilige Randrouter erreichbaren Netzwerke durch das Netz propagiert. Auf diese Weise erfährt der Router D, welche Netzwerke er über die Randrouter B bzw. C erreichen kann. Er ordnet deshalb diesen Netzwerkadressen nach Maßgabe der durch die zentrale Vorrichtung übermittelten Informationen nächste Hops zu. Die resultierende Routingtabelle FIB (FIB: steht für forwarding information base) ist in der Figur gezeigt. Den Netzwerkadressen P1 bis P3 werden die nächsten Hops E und G und den Netzwerkadressen P4 bis P6 die nächsten Hops F und G zugeordnet. Die in der Figur dargestellte Tabelle FIB zeigt nur einen sehr kleinen Ausschnitt aus einer realistischen Routingtabelle. Tatsächliche Routingtabellen sind weit umfangreicher.
Durch die Erfindung muss nur eine einfache Zuordnung der den Randroutern zur Verfügung stehenden Netzwerkadressen zu durch die zentrale Vorrichtung vorgegebenen nächsten Hops bzw. vorgegebenen Routen gemacht werden. Es braucht keine vollständige Routenberechnung bei jedem der Knoten stattzufinden.

Claims

Verfahren zur Berechnung einer Routingtabelle (FIB) für ein Routing innerhalb eines mit Knoten (A, .., G) und Links gebildeten Kommunikationsnetzes, bei dem – eine zentrale Berechnung von Routen zwischen jeweils einem netzinternen Anfangs- und Endknoten vorgenommen wird, – wenigstens einem Knoten (D) des Netzes Informationen über die berechneten Routen kommuniziert werden, – durch den Knoten (D) mittels eines Routingprotokolls eine Routingtabelle (FIB) für das Routing von Paketen aufgebaut wird, indem Zieladressen von zu transportierenden Paketen den berechneten Routen zugeordnet werden.
Verfahren nach Anspruch 1, dadurch gekennzeichnet, dass die Informationen über die berechneten Routen eine eindeutige Kennzeichnung für Endknoten (B, C) und für das Routing zu diesen Endknoten (B, C) zu verwendende nächste Knoten umfassen.
Verfahren nach Anspruch 1 oder 2, dadurch gekennzeichnet, dass zumindest der Anfangsknoten oder Endknoten (B, C) ein Randknoten ist.
Verfahren nach einem der vorhergehenden Ansprüche, dadurch gekennzeichnet, dass – es sich bei dem Routing um ein Mehrwegerouting handelt und zwischen dem Anfangs- und Endknoten eine Mehrzahl von Routen berechnet werden.
Verfahren nach Anspruch 4, dadurch gekennzeichnet, dass – eine zentrale Bestimmung von Verkehrsverteilgewichten zur Steuerung der Aufteilung von Verkehr auf alternativ verfügbare Routen vorgenommen wird, – dem Knoten (D) die Verkehrsverteilgewichte kommuniziert werden, und – die Routingtabelle (FIB) nach Maßgabe der Verkehrsverteilgewichte aufgebaut wird.
Verfahren nach Anspruch 4 oder 5, dadurch gekennzeichnet, dass es sich bei dem Mehrwegerouting um ein Routing handelt, bei dem die Anzahl der alternativen abgehenden Links für das Routing zu dem Endknoten (B, C) für eine maximale Anzahl von inneren Knoten gleich oder größer zwei ist.
Verfahren nach Anspruch 6, dadurch gekennzeichnet, dass – der Knoten (D) ein inneren Knoten des Kommunikationsnetzes ist, für den nur ein abgehender Link zu dem Endknoten (B, C) gegeben ist, – zentral eine Verbindung des inneren Knoten zu einem weiteren Knoten bestimmt wird, welche im regulären Betrieb vom inneren Knoten nicht als alternativer Link im Sinne von Mehrwegerouting verwendet wird, – die Verbindung zentral für den Fall eines Ausfalls des von dem inneren Knoten abgehenden Links als von dem inneren Knoten abgehender Link für das Routing von Paketen zu dem Endknoten (B, C) bestimmt wird (Joker-Link), – der Joker-Link dem Knoten kommuniziert wird und bei dem Aufbau der Routingtabelle berücksichtigt wird.
Verfahren nach einem der vorhergehenden Ansprüche, dadurch gekennzeichnet, dass – das Routingprotokoll durch das OSPF (open shortest path first) oder das IS-IS (intermediate system to intermediate system) gegeben ist.
Verfahren nach einem der vorhergehenden Ansprüche, dadurch gekennzeichnet, dass – das Verfahren für eine Vielzahl von Knoten des Kommunikationsnetzes durchgeführt wird.
Verfahren nach einem der vorhergehenden Ansprüche, dadurch gekennzeichnet, dass – das die zentrale Berechnung bzw. Bestimmung durch eine dedizierte Vorrichtung (NCS) erfolgt.
Vorrichtung zur Berechnung einer Routingtabelle (FIB) für ein Routing innerhalb eines mit Knoten (A, .., G) und Links gebildeten Kommunikationsnetzes, welche – eine zentrale Vorrichtung (NCS) mit Mitteln zur Berechnung von Routen zwischen jeweils einem netzinternen Anfangs- und Endknoten umfasst, – einen Knoten (D) mit Mitteln zum Aufbau einer Routingtabelle (FIB) mittels eines Routingprotokolls umfasst, und – Mittel zur Kommunikation zwischen der zentralen Vorrichtung (NCS) und dem Knoten (D) umfasst.
Vorrichtung nach Anspruch 11, dadurch gekennzeichnet, dass – die Mittel zur Kommunikation zwischen der zentralen Vorrichtung (NCS) und dem Knoten (D) durch ein Kommunikationsprotokoll gegeben sind.
Vorrichtung nach Anspruch 11 oder 12, dadurch gekennzeichnet, dass – es sich bei dem Routing um eine Mehrwegerouting handelt und die zentrale Vorrichtung (NCS) Mittel zur Bestimmung von Verteilungsgewichten umfasst.
Vorrichtung nach einem der Ansprüche 11 bis 13, dadurch gekennzeichnet, dass – durch das Kommunikationsprotokoll Routen oder Verteilungsgewichte von der zentralen Vorrichtung (NCS) an den Knoten (D) kommunizierbar sind.