Longest Prefix Match

Pentru a determina prefixul dintr-o adresă IP și o mască, putem folosi următoarea operație pe biți: ip & mask. De exemplu:

 Adresa IP     Mask            Prefix
10.20.30.4 & 255.255.255.0 = 10.20.30.0

Algoritmul are o specificație relativ simplă:

• Routerul caută în tabela de rutare intrările care fac match pe adresa IP destinație din pachetul IPv4. (ip & mask) == prefix
• Dintre toate rutele pe care s-a făcut match în etapă anterioară, este aleasă ruta cea mai specifică (adică ruta cu prefixul cel mai mare). Dacă două rute au aceeași specificitate, se va folosi ruta cu cel mai mic metric.

Un exemplu este cel din următoarea imagine, în care ruta a doua este cea mai specifică și următorul hop este conectat pe interfața S1.

Ruta 1 nu face match deoarece în acest caz (destIp & mask) != prefix. În schimb ruta 2 și 3 fac match. Totuși, după cum vedem și în imagine, ruta 2 este mai specifică.

O posibilă implementare în O(n) a algoritmului este următoarea:

// Avem o tabela de rutare table {prefix, next_hop, mask, interface}
// tabela trebuie sortata descrescator prefix si masca
// qsort((void *)table, table_len, sizeof(struct route_table_entry), comparator); 

for (int i = 0; i < table_len; i++) {

    /* Cum tabela este sortată, primul match este prefixul ce mai specific */
    if (table[i].prefix == (target_ip & mask)) {
      return &table[i];
    }
}