Как отсортировать IP-адреса в таблице trie?

Я хочу сделать немного кода, чтобы иметь небольшую «таблицу маршрутизации» в моей программе Go.

Я использую левые красно-черные деревья с http://github.com/petar/GoLLRB package, и в основном он работает после того, как немного повозился с ним, однако я подозреваю, что неправильно сортирую префиксы IP при создании дерева. Функция «меньше чем», которую я использовал экспериментально,

func lessRoute(a, b interface{}) bool {
    aNet := a.(Route).Net
    bNet := b.(Route).Net

    for i, a := range aNet.IP {
        if a < bNet.IP[i] {
            return true
        }
        if a > bNet.IP[i] {
            return false
        }
    }
    return false
}

(полный код находится по адресу https://gist.github.com/4283789)

Кажется, это дает мне правильные результаты, но не очень эффективно.

В моем тесте я добавляю маршруты для

AddRouteString(tree, "10.0.0.0/8", 10)
AddRouteString(tree, "10.20.0.0/16", 20)
AddRouteString(tree, "10.21.0.0/16", 21)

а затем при поиске маршрута для 10.22.0.1 он просматривает 10.21.0.0/16 и 10.20.0.0/16, прежде чем найти правильный результат.

Как я должен заказать свое дерево, чтобы быстрее находить правильные результаты?

Обновление: у @jnml есть отличное предложение о том, как ускорить сравнение IP-адресов (и, возможно, это лучшее, что я могу сделать), но мне кажется, что есть способ извлечь выгоду из длина префикса, чтобы упорядочить дерево, чтобы совпадения можно было найти за меньшее количество шагов. Это то, что я ищу.


go cidr algorithm routing binary-tree
person Ask Bjørn Hansen    schedule 14.12.2012    source источник

Ответы (1)


arrow_upward
1
arrow_downward

Я бы, наверное, написал:

if bytes.Compare([]byte(a), []byte(b)) < 0 {
        // ... whatever to do when address a < b (lexicographically)
}

Или для компаратора дерева:

func lessRoute(a, b interface{}) bool {
        return bytes.Compare([]byte(a.(Route).Net.IP), []byte(b.(Route).Net.IP)) < 0
}

bytes.Compare() задокументировано здесь.

person zzzz    schedule 14.12.2012
comment
Ах, да – это сделает сравнение намного быстрее. Моя забота, однако, заключается в том, как заказать дерево; похоже, что есть что-то, что можно сделать, используя преимущества длины префикса. - person Ask Bjørn Hansen; 14.12.2012
comment
Современные процессоры будут загружать весь IP-адрес в кэш L1 и обрабатывать общий префикс быстрее, чем вы сможете вычислить, где начинается общий префикс. - person TomOnTime; 18.10.2017