Здравствуйте, netch80, Вы писали:

S>> Спасибо буду знать. Я про то, что никто не будет просто чесать по всем адресам, будет алгоритм для как минимум бинарного поиска.
S>> В твоем примере это деревья.

N>Да.

S>> Shmj то пишет, что проблемы в процессоре. При бинарном поиске все эти затраты нивелируются

N>До какой степени они нивелируются?

N>Возьмём линк на 40Gbit/s, это нормальная скорость для провайдера мирового масштаба. Средний размер пакета очень плохо гуглится. Я считал 500 байт, но есть неясной авторитетности сообщения про 300 байт. Я готов поверить, потому что сейчас >90% трафика это видео. Возьму 500 байт. Получим 10 миллионов пакетов в секунду на таком линке. Предположим, что это один такой линк для одного процессора. Тогда у него 100 нс на всю обработку одного пакета. Возьмём половину из них на память и что мы смотрим только старшую половину IPv6 адреса — или даже что меньше /48 не смотрим (в смысле, префиксами длиннее), потому что даже PI не выдают дробнее /48. Тогда 6 байт на поиск в глобальном раутинге. Пусть у нас дерево побайтное. Получится 8 наносекунд на один шаг поиска, включая работу процессора. Оставим 5 нс на ожидание памяти.

N>Вот теперь начинается интересное. Для DRAM операция закрытия текущей строки и открытия новой в лучших современных образцах это 30 нс, а совсем недавно было нормально и 50 нс. DRAM — в топку, повторюсь уже в 4й раз в этой теме. Процессору нужно 64-128MB на IPv4+IPv6 fullview (и то не уверен, что я не пропустил какие-то важные детали, тогда ещё больше), и это всё static RAM. Ну, наверно, успеваем, если одно чтение из памяти отрабатывает за 1нс или меньше.

N>Теперь корректируем на 300 байт на пакет, на 100GBit/s линк (есть и такие уже), на рост таблиц BGP (при полном переходе на IPv6 его таблица минимум удвоится, если не дойдёт до миллиона, как сейчас с IPv4). Медленно охреневаем от числовых требований и понимаем, что без подхода типа "8 параллельных процессоров на каждой сетевой карте с полным объёмом данных в собственной памяти" это не работает. А я ещё не начал считать внутренние кросс-шины, сколько и как они должны пропустить...

Опять же когда ты используешь деревья для поиска, то для понимания больше меньше, тебе не надо сравнивать полностью 16 байт. В большинстве случаев хватает и 8.
Только в конце поиска тебе придется полностью сравнивать.
Опять же посмотрим во сколько раз производительность процессоров и памяти выросла и количество ядер. При этом 64 битные процессоры массово появились относительно недавно.

Здравствуйте, netch80, Вы писали:

S>> Спасибо буду знать. Я про то, что никто не будет просто чесать по всем адресам, будет алгоритм для как минимум бинарного поиска.
S>> В твоем примере это деревья.

N>Да.

S>> Shmj то пишет, что проблемы в процессоре. При бинарном поиске все эти затраты нивелируются

N>До какой степени они нивелируются?

N>Возьмём линк на 40Gbit/s, это нормальная скорость для провайдера мирового масштаба. Средний размер пакета очень плохо гуглится. Я считал 500 байт, но есть неясной авторитетности сообщения про 300 байт. Я готов поверить, потому что сейчас >90% трафика это видео. Возьму 500 байт. Получим 10 миллионов пакетов в секунду на таком линке. Предположим, что это один такой линк для одного процессора. Тогда у него 100 нс на всю обработку одного пакета. Возьмём половину из них на память и что мы смотрим только старшую половину IPv6 адреса — или даже что меньше /48 не смотрим (в смысле, префиксами длиннее), потому что даже PI не выдают дробнее /48. Тогда 6 байт на поиск в глобальном раутинге. Пусть у нас дерево побайтное. Получится 8 наносекунд на один шаг поиска, включая работу процессора. Оставим 5 нс на ожидание памяти.

N>Вот теперь начинается интересное. Для DRAM операция закрытия текущей строки и открытия новой в лучших современных образцах это 30 нс, а совсем недавно было нормально и 50 нс. DRAM — в топку, повторюсь уже в 4й раз в этой теме. Процессору нужно 64-128MB на IPv4+IPv6 fullview (и то не уверен, что я не пропустил какие-то важные детали, тогда ещё больше), и это всё static RAM. Ну, наверно, успеваем, если одно чтение из памяти отрабатывает за 1нс или меньше.

N>Теперь корректируем на 300 байт на пакет, на 100GBit/s линк (есть и такие уже), на рост таблиц BGP (при полном переходе на IPv6 его таблица минимум удвоится, если не дойдёт до миллиона, как сейчас с IPv4). Медленно охреневаем от числовых требований и понимаем, что без подхода типа "8 параллельных процессоров на каждой сетевой карте с полным объёмом данных в собственной памяти" это не работает. А я ещё не начал считать внутренние кросс-шины, сколько и как они должны пропустить...

Опять же когда ты используешь деревья для поиска, то для понимания больше меньше, тебе не надо сравнивать полностью 16 байт. В большинстве случаев хватает и 8.
Только в конце поиска тебе придется полностью сравнивать.
Опять же посмотрим во сколько раз производительность процессоров и памяти выросла и количество ядер. При этом 64 битные процессоры массово появились относительно недавно.
И тоже крику было много. Однако живем и в мобильниках давно существует.