Browse Prior Art Database

Ein einfaches IP-Routing-Verfahren mit optimiertem Backtracking

IP.com Disclosure Number: IPCOM000125206D
Published in the IP.com Journal: Volume 5 Issue 6A (2005-06-20)
Included in the Prior Art Database: 2005-Jun-20
Document File: 4 page(s) / 186K

Publishing Venue

Siemens

Related People

Juergen Carstens: CONTACT

Abstract

IP-Router dienen als Vermittlungsknoten im Internet, wenn sie IP-Pakete von einem Absender zu einem Empfaenger weiterleiten. Auf einen Router, der ein solches IP-Paket empfaengt, kommt die Aufgabe zu, aus einer Vielzahl von Nachbar-Routern den am Besten geeigneten auszusuchen, an den das Paket weitergeleitet wird. Dazu muss der Router auch unter der Vielzahl seiner Ausgaenge (Ports) denjenigen aussuchen, ueber den der ermittelte Nachbar-Router am Besten erreichbar ist. Der Router erfuellt diese Aufgabe mit Hilfe einer Routing-Tabelle, die Adressinformationen der fuer den Router sichtbaren Netzumgebung enthaelt. Solch eine Routing-Tabelle ist in der Regel sehr umfangreich, und ihre Verarbeitung wird vom Router mit Hilfe von bestimmten Suchalgorithmen realisiert, z.B. PATRICIA-Suchbaeumen (Algorithmus vom Radix-Typ) oder Hash-Tabellen (auf Tabellen basierender Algorithmus). Ein Nachteil dieser Methoden ist, dass der grosse IP-Adressbereich nicht eindeutig auf reduzierte Adressbereiche abgebildet werden kann, ohne dass einschraenkende Zusatzbedingungen mit einbezogen werden. Im Folgenden wird ein Routing-Algorithmus beschrieben, der fuer Netze geeignet ist, fuer die kein Online-Update der Routing-Tabelle vorgesehen ist und deren Adressen ein festes Darstellungsformat besitzen, die also, wie die IP-Adressen, als Integerzahlen darstellbar sind.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 25% of the total text.

Page 1 of 4

S

Ein einfaches IP-Routing-Verfahren mit optimiertem Backtracking

Idee: Dr. Karl Bernhardi, DE-Muenchen

IP-Router dienen als Vermittlungsknoten im Internet, wenn sie IP-Pakete von einem Absender zu einem Empfaenger weiterleiten. Auf einen Router, der ein solches IP-Paket empfaengt, kommt die Aufgabe zu, aus einer Vielzahl von Nachbar-Routern den am Besten geeigneten auszusuchen, an den das Paket weitergeleitet wird. Dazu muss der Router auch unter der Vielzahl seiner Ausgaenge (Ports) denjenigen aussuchen, ueber den der ermittelte Nachbar-Router am Besten erreichbar ist. Der Router erfuellt diese Aufgabe mit Hilfe einer Routing-Tabelle, die Adressinformationen der fuer den Router sichtbaren Netzumgebung enthaelt. Solch eine Routing-Tabelle ist in der Regel sehr umfangreich, und ihre Verarbeitung wird vom Router mit Hilfe von bestimmten Suchalgorithmen realisiert, z.B. PATRICIA-Suchbaeumen (Algorithmus vom Radix-Typ) oder Hash-Tabellen (auf Tabellen basierender Algorithmus). Ein Nachteil dieser Methoden ist, dass der grosse IP- Adressbereich nicht eindeutig auf reduzierte Adressbereiche abgebildet werden kann, ohne dass einschraenkende Zusatzbedingungen mit einbezogen werden.

Im Folgenden wird ein Routing-Algorithmus beschrieben, der fuer Netze geeignet ist, fuer die kein Online-Update der Routing-Tabelle vorgesehen ist und deren Adressen ein festes Darstellungsformat besitzen, die also, wie die IP-Adressen, als Integerzahlen darstellbar sind.

Das Verfahren stellt die in einzelne Netze und Subnetze unterteilten Adressbereiche als Teilintervalle im gesamten Adressraum, in Binaerdarstellung von 0 bis 232, dar (Abb. 1). Im Folgenden werden diese Teilintervalle als Netzintervalle bezeichnet. Fuer die Netzintervalle wird die Binaerdarstellung benutzt. Sie werden durch die Anzahln (=Laenge der Netz- bzw. Subnetzadresse) und Werte der signifikanten Bits (Binaerzeichen im Ziffernbereich 1 bis n) definiert. m ist die Bitposition im Bereich <= n. Die Darstellung der einzelnen Netzintervalle erfolgt linksbuendig. Als Netzintervalle werden nur die Intervalle zugelassen, die im insignifikanten Bereich alle Ziffernkombinationen annehmen koennen. Diese bilden das gesamte Adressvolumen des (Sub-)Netzes A.

Aus einem gegebenen Netzintervall A mit der Laenge n lassen sich ueber- und untergeordnete Netzintervalle ableiten. Das A uebergeordnete Netzintervall A* mit der Laenge n* < n entspricht dem von der Laenge n auf die Laenge n* verkuerzten Praefix von A. Ein A untergeordnetes Netz A** (also ein Subnetz von A) laesst sich durch Verlaengern des Praefix des signifikanten Bereichs von A, d.h., in der Binaerdarstellung durch Hinzufuegen weiterer signifikanter Bits an Bitpositionen m** > n, bilden.

Zwei Eigenschaften zeichnen die auf diese Weise gebildeten Netzintervalle aus:

1) Es existiert eine Hierarchie-Eigenschaft: Fuer ueber- und untergeordnete Netzintervalle gilt:

min(A*) <= min(A) <= min(A**),

max(A*) >= max(A) >= max(A**).

2) Voneinander versch...