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

SK>>>Что экономить? Какие вычисления производятся над ip адресами?
S>>Да хотя бы поиск по адресам в памяти.
SK>Зачем поиск?
SK>В процентном отношении как часто производится эта странная операция?

99.9%. Если мы говорим о магистральном раутере, для которого это основной вид работы.
Я уже писал: в них операции с младшей половиной адреса, если это транзит, а не отправка на локальный интерфейс, просто отключены программно.
Глобальный раутинг по префиксам длиннее /64 в них не поддерживается (на самом деле, и на таком во многих не поддерживается, минимум в таких /48, но для одного машинного слова разницы уже нет).

Конечному хосту, конечно, пофиг — ему хоть 512 бит, это заметно не замедлит. Но его проблемы тут не ключевые.

S>>Притом что такая избыточность ничем не оправдана.
SK>Эмоции убери в сторону. Избыточность ещё не доказана.

Доказана тем, что никто не смог выдвинуть достойных аргументов в её пользу. Лучшее, что есть, это "уже сделали, менять поздно".

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

SK>>Зачем поиск?
SK>>В процентном отношении как часто производится эта странная операция?

S>Приходит на роутер IP-пакет. В нем указан IP-адрес назначения. Вам нужно бинарным поиском по таблице найти куда его отправлять дальше.

Это работает немножко совсем не так и на эту операцию которую ты имеешь в виду тратится 1 такт процессора. вычислительной мощности тратится 0 (zero).

S>>> И это на всех уровнях, в т.ч. даже если вашей прикладной программе, не сетевой — есть черный список IP-адресов.
SK>>Зачем НЕ сетевой программе знать о каких-то ip адресах?

S>Хотя бы чтобы проверить по черному списку IP-адресов. Или для защиты от DDOS.

Для защиты НЕ сетевой программы? Не понимаю.

Тогда что ты называешь "НЕ сетевой программой" а что "сетевой программой" ?

Все проблемы от жадности и глупости

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

SK>>Зачем поиск?
SK>>В процентном отношении как часто производится эта странная операция?

N>99.9%. Если мы говорим о магистральном раутере, для которого это основной вид работы.
N>Я уже писал: в них операции с младшей половиной адреса, если это транзит, а не отправка на локальный интерфейс, просто отключены программно.
N>Глобальный раутинг по префиксам длиннее /64 в них не поддерживается (на самом деле, и на таком во многих не поддерживается, минимум в таких /48, но для одного машинного слова разницы уже нет).

В раутере этим аппаратно занимается ASIC (ПЛМ), таки специализированный "128 битный процессор".

Тут у нас очевидная проблема, что Shmj думает что в раутеры ставят х86_64 пентиумы процессоры общего назначения под управлением линукса операционной системы общего назначения.

S>>>Притом что такая избыточность ничем не оправдана.
SK>>Эмоции убери в сторону. Избыточность ещё не доказана.

N>Доказана тем, что никто не смог выдвинуть достойных аргументов в её пользу. Лучшее, что есть, это "уже сделали, менять поздно".

Сделали с учетом недостатков IPv4 с большим запасом. что б не возвращаться к этому вопросу ближайшие 50 лет.

Единственный реальный недостаток — недружелюбный к человеку формат адреса (трудно читаемый, трудно произносимый, не запоминаемый).

Все проблемы от жадности и глупости

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

S>>Тебя так 8 байт волнуют? Хранение это вообще проблема?
S>>Ладно бы там еще конец 20 го века, но сейчас ...
S>> Ты бы лучше свою энергию в другое русло направил!

S>Главным образом — архитектура процессора. 8 байт — это 64 битный процессор. А 16 байт — это спец. архитектура, которая не совместима со стандартной и ее нужно делать отдельно только для обработки IP-адресов.

S>В стандартном С есть нейтивный тип 8 байт, но нет 16 байт — даже в С вам нужно городить структуру для IP + и операции с ней реализовывать на базе операций с 8-байтным типом.

Ты серьезно? Там поиск по хэштаблице. Какая разница?

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

S>Напиши на C++ поиск по IP-адресам из черного списка. Сначала напиши для 8-байтных адресов (а это делается нейтивным типом), потом для 16 байт. Сравни скорость работы.
Зачем? Скорости QSet<QHostAddress> не хватает?

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

SK>Это работает немножко совсем не так и на эту операцию которую ты имеешь в виду тратится 1 такт процессора. вычислительной мощности тратится 0 (zero).

Обясни как на сравнение 16 байтных значений тратиться 1 такт, если нет такого нейтивного типа в архитектуре процессора.

SK>Для защиты НЕ сетевой программы? Не понимаю.
SK>Тогда что ты называешь "НЕ сетевой программой" а что "сетевой программой" ?

Низкоуровневая сетевая — которая работает на уровне протокола IP или хотя бы TCP/UDP.

Просто сайт какой — может просто получать IP клиента и искать его в черном списке. И намного проще будет, если в качестве IP адреса можно задействовать нейтивный для процессора тип — 64 бита.

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

S>>В стандартном С есть нейтивный тип 8 байт, но нет 16 байт — даже в С вам нужно городить структуру для IP + и операции с ней реализовывать на базе операций с 8-байтным типом.
S> Ты серьезно? Там поиск по хэштаблице. Какая разница?

Разница в том что 8 байт — это нейтивный для процессора тип, вмещается в обычный регистр. А 16 байт — нет.

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

S>>Напиши на C++ поиск по IP-адресам из черного списка. Сначала напиши для 8-байтных адресов (а это делается нейтивным типом), потом для 16 байт. Сравни скорость работы.
BFE>Зачем? Скорости QSet<QHostAddress> не хватает?

Скорости всегда мало — представь что запросов миллионы в секунду. И каждый IP нужно как-то обработать. Естественно нейтивно поддерживаемый процессором тип будет на порядки быстрее.

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

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

S>>>В стандартном С есть нейтивный тип 8 байт, но нет 16 байт — даже в С вам нужно городить структуру для IP + и операции с ней реализовывать на базе операций с 8-байтным типом.
S>> Ты серьезно? Там поиск по хэштаблице. Какая разница?

S>Разница в том что 8 байт — это нейтивный для процессора тип, вмещается в обычный регистр. А 16 байт — нет.
Ты как то про хэш таблицу пропустил. Поместится в 2 регистра! Или регистров не хватает?

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

N>Аналогично, возьмём, например, сравнение по маске. Пусть у тебя есть три параметра: сравниваемый адрес, адрес образца и длина префикса образца (больше 0). Вариант для одного целого: вычислил маску: ~((1ul<<(64-pl))-1ul), и сравнил. Как будет выглядеть вариант для 128 бит? Если нет нативной поддержки uint128_t, будет явное ветвление в коде, дорого. Если есть uint128_t, будет неявное ветвление, с тем же результатом. Можешь посмотреть сам на компиляторный выхлоп.

Чёйта?

Заксорь сравниваемый адрес с образцом, пословно. Потом заенди с маской, тоже пословно. Потом результирующие слова, 2 64-битных или 4 32-биных, заорь побитно промеж собой. Получишь в итоге ноль или не ноль, результат твоего сравнения. Никаких промежуточных ветвлений, плюс промежуточные операции еще и запараллелиться имеют шанс в процессоре.

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

S>>Разница в том что 8 байт — это нейтивный для процессора тип, вмещается в обычный регистр. А 16 байт — нет.
S> Ты как то про хэш таблицу пропустил. Поместится в 2 регистра! Или регистров не хватает?

А вычислять хеш каждый раз? Разрешать коллизии?

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

vsb>>Header Checksum: 16 bits (в низлежащих протоколах контрольная сумма есть, это не нужно)

N>В IPv6 устранили, да.

Вероятно потому, что не осталось практически значимых сред передачи пакетов, которые не делают хотя бы CRC32.

IP-ная чексумма, это, конечно, что-то с чем-то...

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

S>>>Напиши на C++ поиск по IP-адресам из черного списка. Сначала напиши для 8-байтных адресов (а это делается нейтивным типом), потом для 16 байт. Сравни скорость работы.
BFE>>Зачем? Скорости QSet<QHostAddress> не хватает?

S>Скорости всегда мало — представь что запросов миллионы в секунду. И каждый IP нужно как-то обработать. Естественно нейтивно поддерживаемый процессором тип будет на порядки быстрее.

Ответ от ChatGPT:

6. Алгоритм CAM (Content-Addressable Memory)
CAM — это специальная память, используемая в маршрутизаторах для поиска совпадений в один такт, что делает её крайне быстрой.
Адрес назначения пакета вводится в CAM, и она сразу возвращает префикс с наибольшей длиной совпадения.

От себя добавлю, что если для поиска использовать B-Tree с ключом в байт, то разница между 8-байтовым адресом и 16 байтовым адресом будет всего 8 операций сложения и 8 операций сравнения, что не выглядит чем-то из-за чего стоит переживать.

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

SK>>Это работает немножко совсем не так и на эту операцию которую ты имеешь в виду тратится 1 такт процессора. вычислительной мощности тратится 0 (zero).

S>Обясни как на сравнение 16 байтных значений тратиться 1 такт, если нет такого нейтивного типа в архитектуре процессора.


0) сравниваются биты.

1) такой тип в архитектуре процессора есть.

Все проблемы от жадности и глупости

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

B>ввести айди для людей и сдлеать инет адреса, связаные с айди, для девайсов — географические координаты

А как коммуницировать с движущимся девайсом?

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

S>>>Разница в том что 8 байт — это нейтивный для процессора тип, вмещается в обычный регистр. А 16 байт — нет.
S>> Ты как то про хэш таблицу пропустил. Поместится в 2 регистра! Или регистров не хватает?

S>А вычислять хеш каждый раз? Разрешать коллизии?

Это сложно? Или ты хочешь искать проходя по всем адресам?
Зачем хэш таблицу то придумали?

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

SK>>>Зачем поиск?
SK>>>В процентном отношении как часто производится эта странная операция?

N>>99.9%. Если мы говорим о магистральном раутере, для которого это основной вид работы.
N>>Я уже писал: в них операции с младшей половиной адреса, если это транзит, а не отправка на локальный интерфейс, просто отключены программно.
N>>Глобальный раутинг по префиксам длиннее /64 в них не поддерживается (на самом деле, и на таком во многих не поддерживается, минимум в таких /48, но для одного машинного слова разницы уже нет).

SK>В раутере этим аппаратно занимается ASIC (ПЛМ), таки специализированный "128 битный процессор".

Во-первых, пусть ASIC — и в нём всё равно младшую часть адреса не проверяют, пока не приходит время разбираться, куда же раутить именно на непосредственно подключенный интерфейс (а не на уже известный шлюз следующего хопа).
Потому что держать полные 128 бит в таблицах для этого ASIC — дорого и бессмысленно, сокращение в 2 раза всей памяти — и тех ассоциативных блоков, которые срабатывают на каждый пакет — достаточно важно, чтобы от него избавляться.

Во-вторых, далеко не всё может пройти этим путём. Разработчики раутеров, конечно, пытаются вынести по максимуму на уровень FPGA/ASIC/etc., но чуть шаг в сторону от привычного пути — привет, центральный процессор и просадка по CPS в 3-4 раза (даже если тому процессору работа вылизана до предела).

SK>Тут у нас очевидная проблема, что Shmj думает что в раутеры ставят х86_64 пентиумы процессоры общего назначения под управлением линукса операционной системы общего назначения.

Дальше линейных процессоров карт таки стоят почти что процессоры общего назначения. Разумеется, не x86, потому что там нужен BE хотя ASA делались именно на x86!
У Cisco в моделях 90-х вообще стоял M68k, дальше они перешли на MIPS. Сейчас, по слухам, какие-то ARM, я давно не следил сам.
Существенное отличие — в доступе к памяти. Память кэша раутинга она static RAM с явным управлением от процессора (а не неявным, как в обычных общего назначения, где ты просто видишь кэш).

S>>>>Притом что такая избыточность ничем не оправдана.
SK>>>Эмоции убери в сторону. Избыточность ещё не доказана.

N>>Доказана тем, что никто не смог выдвинуть достойных аргументов в её пользу. Лучшее, что есть, это "уже сделали, менять поздно".

SK>Сделали с учетом недостатков IPv4 с большим запасом. что б не возвращаться к этому вопросу ближайшие 50 лет.

Да тут не 50, тут на 100 размахнулись. И вот это плохо — потому что за это время точно что-то должно было измениться в подходе.

SK>Единственный реальный недостаток — недружелюбный к человеку формат адреса (трудно читаемый, трудно произносимый, не запоминаемый).

Не единственный, если на то пошло.
Надо было как минимум ещё порты расширить до 32 бит.
Но они почему-то не решились менять и заголовки транспортных уровней.

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

N>>Аналогично, возьмём, например, сравнение по маске. Пусть у тебя есть три параметра: сравниваемый адрес, адрес образца и длина префикса образца (больше 0). Вариант для одного целого: вычислил маску: ~((1ul<<(64-pl))-1ul), и сравнил. Как будет выглядеть вариант для 128 бит? Если нет нативной поддержки uint128_t, будет явное ветвление в коде, дорого. Если есть uint128_t, будет неявное ветвление, с тем же результатом. Можешь посмотреть сам на компиляторный выхлоп.

Pzz>Чёйта?

Pzz>Заксорь сравниваемый адрес с образцом, пословно. Потом заенди с маской, тоже пословно.

Спасибо, кэп.
А вот вычисление маски плохо ускоряется.
А сделать заранее маску из длины префикса возможно не всегда. Я об этом.

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

S>>Скорости всегда мало — представь что запросов миллионы в секунду. И каждый IP нужно как-то обработать. Естественно нейтивно поддерживаемый процессором тип будет на порядки быстрее.

BFE>Ответ от ChatGPT:
BFE>

BFE>6. Алгоритм CAM (Content-Addressable Memory)
BFE> CAM — это специальная память, используемая в маршрутизаторах для поиска совпадений в один такт, что делает её крайне быстрой.
BFE> Адрес назначения пакета вводится в CAM, и она сразу возвращает префикс с наибольшей длиной совпадения.

ChatGPT такой ChatGPT
Этот ответ не учитывает, что поиск по такой памяти чудовищно дорогой по энергии.
CAM — это, несколько упрощённо, как L1 кэш в обычном процессоре, который полноассоциативный. (Упрощение потому, что в обычном кэше всегда одно совпадение по адресу, а тут может быть несколько, из них берётся лучшее.) Почему размер L1 кэша только-только перевалил за 64KB и подходит к 128? Причём это строками по 64 байта (стандарт сейчас почти везде), то есть это 2048 строк? Потому что если её увеличивать, то процессор закипит к хренам и расплавится. И это при поиске по длине ключа, например, 44-6=38 бита (если длина физического адреса 44 бита). А при 64? 128?

Фактически, в линейном процессоре одной карты в раутере объём той CAM это единицы тысяч строк. Дальше идут, опять же упрощая, аналоги следующих уровней кэша, как L2 и L3 (у которых уже нет полной ассоциативности), и процессорные блоки, которые их перезаполняют.

А основная засада тут в том, что в отличие от кэша для обычных процессорных задач, тут сильно меньше временно́й локальности (temporal locality), без которой кэш вообще бесполезен. Когда процессор ползёт по странице кода исполняя программу, там одна строка содержит десяток команд. Когда TLB miss вызывает поиск по иерархии page tables, там одним махом сразу решается 4KB (минимум для x86). Когда у тебя через один раутер ползёт сотня тысяч видеопотоков, каждый из которых это один IP пакетик раз в 10 или 20 мс, всей этой системе тупо плохо.
(Раньше сильно любили кэшировать характеристики конкретного flow, который определялся и парой IP, и портами. Но это работает на уровне ну до 1000 клиентов, и то не очень.)
Фактически, нужные количественные характеристики достигаются там жёсткой параллельностью плюс скоростью памяти (DRAM уже непригодна).

И это ещё и усложняется тем, что запись такого кэша должна содержать не только целевой интерфейс, а ещё и довески в виде можно/нельзя, меток, и прочего.
Cisco свой CEF тут вылизывала несколько лет, прежде чем он надёжно заработал, а до того админы старались его выключать.

BFE>От себя добавлю, что если для поиска использовать B-Tree с ключом в байт, то разница между 8-байтовым адресом и 16 байтовым адресом будет всего 8 операций сложения и 8 операций сравнения, что не выглядит чем-то из-за чего стоит переживать.

Что-то очень странное и неадекватное говоришь.

Во-первых, в B-Tree ключи используются полной длины. Ты с Trie не перепутал? Там частичные ключи таки структурированы мелкими порциями, по биту или байту.

Во-вторых, 8 дополнительных лукапов на скорости нормального современного магистрального раутера могут уложиться в доступные временны́е рамки только при определённых ограничениях, из которых чуть ли не первое это неиспользование DRAM. Возьми ценник на память, умножь на 10 (объективно за счёт того, что на 1 бит не 1 транзистор, а почти десяток) и ещё на 3 (накрутка производителя раутера), посмотри, сколько её нужно на современные потребности (меньше 128MB не рассматриваем) и оцени, сколько нефти придётся выложить провайдеру на такую железяку.
И тогда пролетавшие тут рядом цены типа 47 миллионов деревянных перестают удивлять.

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

S> Ты серьезно? Там поиск по хэштаблице.

Прекратите курить эти опилки, плохой дым получается. Никакие хэш-таблицы непригодны в принципе, потому, что поиск должен срабатывать по _неточному_ совпадению (базовый адрес плюс длина сети покрывает этот адрес) с наиболее длинным префиксом. Хэш-таблицы срабатывают только при полном совпадении.
Всякие AVL/RB/B-tree тоже не годятся, потому что может быть, что совпадает не тот, у кого ближайший базовый адрес, а тот, у кого сеть накрывает этот адрес.

Там Radix tree в бинарном варианте. При совпадении пары baseaddr+prefixlen у двух записей срабатывает метрика (меньше — важнее).
Бывает ещё больше параметров.

Поясняю на примере: пусть есть записи:

10.1.2.0/23 (то есть 10.1.2.0...10.1.3.255)
10.1.0.0/16 (то есть 10.1.0.0...10.1.255.255) с метрикой 10.
10.1.0.0/16 опять же, с метрикой 20.
10.0.0.0/8 (то есть 10.0.0.0...10.255.255.255)
10.1.3.0/27 (то есть 10.1.3.0...10.1.3.31)

Для 10.1.3.4 сработать должен 10.1.3.0/27, потому что у него самый длинный префикс.

Для 10.1.244.1 сработает 10.1.0.0/16 с метрикой 10, базовые адреса и длины префикса одинаковые, включается метрика.

(Метрика задаётся источником. Например 0 — directly connected, 1 — static, дальше идут в определённом порядке внутренние динамические протоколы, потом внешние.)