Longest Prefix Match

Verfahren aus dem Bereich Netzwerk

Longest Prefix Match ist ein einfaches Verfahren aus dem Bereich Netzwerk. Hierbei geht es darum, wie ein Router möglichst effizient eine maximal mögliche Übereinstimmung der Zieladresse mit einer gespeicherten IP-Adresse aus seiner internen Routingtabelle findet. Der Routenalgorithmus kommt dann zum Einsatz, wenn die Routingtabelle mehrere potentiell zur Zieladresse eines Paketes passende Adressbereiche beinhaltet und gehört nach der Ablösung von Netzklassen durch Adressen und frei wählbare Netzmasken (CIDR) zu den Standardverfahren.[1]

Allgemein gilt: Ein Router pflegt intern eine Routingtabelle mit Netzwerkadressen und Netzmasken und einer dazu zugeordneten Schnittstelle, um ein empfangenes Paket weiterleiten zu können. Liegt die Zieladresse in mehreren verfügbaren Subnetzen, so wird der Eintrag mit der längsten Übereinstimmung gewählt.

Das Verfahren kommt sowohl bei IPv4 als auch IPv6 zum Einsatz.[2]

Beispiel

Bearbeiten

Im Folgenden enthalte ein Router eine Routingtabelle mit drei IP-Address-Templates und den zugeordneten Schnittstellen. Es wird ein Paket mit der Zieladresse 198.51.100.78 empfangen, folglich muss eine bestmögliche Auswahl zur Weiterleitung des Paketes getroffen werden. Obwohl es zum Netz 198.51.100.0/24 (Schnittstelle 1) passt, wird das Paket jedoch nur über die Schnittstelle weitergeleitet, die eine maximale Übereinstimmung mit der Zieladresse hat, in diesem Fall die Schnittstelle 2. Zur Adresse der Schnittstelle 3 passt das Paket dagegen nicht, so dass die Netzmaske dieses Eintrags keine Rolle spielt.

Vereinfachte IPv4 Routingtabelle eines Routers

# Netzwerk-Adresse Subnetzmaske
(Präfixlänge)
Schnittstelle
1 198.51.100.0 255.255.255.0 / 24 Schnittstelle 1
2 198.51.100.64 255.255.255.192 / 26 Schnittstelle 2
3 198.51.100.128 255.255.255.192 / 26 Schnittstelle 3

Empfangenes Paket mit der IPv4-Adresse 198.51.100.78

Adresse/Netz (CIDR) Binärdarstellung Übereinstimmung
198.51.100.78/32     11000110.00110011.01100100.01001110
198.51.100.0/24      11000110.00110011.01100100.00000000  24 Bit
198.51.100.64/26     11000110.00110011.01100100.01000000  26 Bit
198.51.100.128/26    11000110.00110011.01100100.10000000  -

Die längste Übereinstimmung mit dem jeweiligen vollständigen fixen Adressteil liegt bei Eintrag #2 vor, nämlich 26 Bit. Weiterleitung des Paketes entsprechend über Schnittstelle  2.

Literatur

Bearbeiten

Einzelnachweise

Bearbeiten
  1. RFC 1519 – Classless Inter-Domain Routing (CIDR). Abschnitt 4.1 (englisch).
  2. RFC 6724 – Default Address Selection for Internet Protocol Version 6 (IPv6). (englisch).