LINUX.ORG.RU

Матчасть по маршрутизации


0

1

Есть такая задачка.

Допустим, есть очередь из писем.

У каждого письма — свой адрес отправки и адрес назначения. Надо максимально эффективно определять почтовые индексы адреса назначения согласно набору правил, формирующемуся динамически, где каждое правило — это функция f(s, d) от адресов отправителя и получателя, возвращающая нужный индекс.

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

Пока что я не придумал ничего лучшего, чем
— правила перебираются по очереди до первого совпадения
— каждое правило имеет счетчик срабатываний
— через каждые N писем правила сортируются по количеству совпадений от большего к меньшему, а счетчики обнуляются.

Может, бывают другие хорошие способы определять эффективность (оптимизация самих правил не в счет)?

★★★★★

Цитируем shimon

согласно набору правил, формирующемуся динамически

можно подробнее?

power
()

Ещё можно(?, нужна доп. информация на счёт ящика) кэшировать ответы от функций f(s,d).

mikki
()
Ответ на: комментарий от power

> согласно набору правил, формирующемуся динамически

Это означает, что правила можно добавлять и удалять прямо в рантайме, вручную либо алгоритмически. Например, если Вася Пупкин уже сотый раз за день пишет Жириновскому о том, как тот его заколебал, вставляется правило отправлять письма от Васи Пупкина к Жириновскому через почтовый индекс 666, где письма жгут не глядя, прямо в мешках.

И для этого конвейер не надо даже ставить на паузу.

shimon ★★★★★
() автор топика

>>набору правил, формирующемуся динамически, где каждое правило — это функция f(s, d) от адресов отправителя и получателя, возвращающая нужный индекс

Точнее сказать, что набор, это множество подфункций исходной функции, полученных сужением исходной функции на неперекрывающиеся подмножества области определения.

mclaudt
()
Ответ на: комментарий от mikki

> Ещё можно(?, нужна доп. информация на счёт ящика) кэшировать ответы от функций f(s,d).

Можно кешировать, но тогда расчет эффективности порядка правил должен еще и учитывать кеш-попадания и кеш-промахи. Становится немножко нетривиально.

Что ли почитать ядро линакса на предмет того, как роутятся пакеты.

shimon ★★★★★
() автор топика
Ответ на: комментарий от mclaudt

> Точнее сказать, что набор, это множество подфункций исходной функции, полученных сужением исходной функции на неперекрывающиеся подмножества области определения.

Можно и так сказать. Факт тот, что количественно-качественный состав этих неперекрывающихся множеств может изменяться в зависимости от многих факторов, самый весомый — желание левой пятки владельца конвейера.

shimon ★★★★★
() автор топика
Ответ на: комментарий от mclaudt

Хотя тут неперекрываемость несущественна, наоборот, хорошо если будет дублироваться.

Считается, что порядок правил не имеет значения.

Странно, должен иметь. В нем и состоит залог улучшения. Правила ведь обрабатываются последовательно. Можно накопить статистику и посмотреть распределение номера шага, на котором происходит окончательное принятие решения. Если этот номер распределен по геометрическому распределению (схема Бернулли), то что-то улучшить вряд ли получится. Если наблюдается отклонение от геометрического распределения, то имеет смысл переставить порядок обработки правил.

mclaudt
()
Ответ на: комментарий от mclaudt

Но это верно для некого устаканившегося неизменного набора правил и для допущения одинаковой вероятности письма попасть под то или иное правило.

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

mclaudt
()
Ответ на: комментарий от mclaudt

> Странно, должен иметь.

В этом смысле — да. Я имел в виду то, что в каком порядке правила не применишь, одной паре (s, d) должен всегда соответствовать один индекс.

shimon ★★★★★
() автор топика
Ответ на: комментарий от mclaudt

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

Именно поэтому — эмпирический способ: каждые N писем выталкиваем самые частоиспользуемые функции вверх.

shimon ★★★★★
() автор топика
Ответ на: комментарий от shimon

Что ли почитать ядро линакса на предмет того, как роутятся пакеты.

В ядре такой задачи не стоит, там либо ~fifo, либо как указано в статических правилах.

mikki
()

ИМХО, самое простое, переставлять сработавшее правило в начало списка, каждый раз. Потому что, если у вас упорядочивания списка будет достаточно часто, а правил будет много, то сработавших правил будет не много, а сортировать весь список.

Относительно кеширования, непонятно, как часто у вас повторяется пара (s,d), в случае маршрутизации, там вполне ожидаемо, что если прошёл один пакет от a к b, то скоро последуют и другие.

mky ★★★★★
()
Ответ на: комментарий от mky

> ИМХО, самое простое, переставлять сработавшее правило в начало списка, каждый раз.

Если переставлять одно правило по накладным расходам так же, как сотню правил, то лучше переставить сотню.

shimon ★★★★★
() автор топика
Ответ на: комментарий от shimon

>Если переставлять одно правило по накладным расходам так же, как сотню правил

Мда, подробности из вас нужно тащить клещами :)

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

Вобще, вы бы определились, как часто могут быть повторы (s, d), что более затратно --- проверка правила или его перестановка и насколько.

mky ★★★★★
()
Ответ на: комментарий от mky

> Не знаю, в каком виде у вас хранятся правила, думал, что что-то наподобие связного списка. И в случае сортировки, не знаю, сколько перестановок вы будете делать.

Так как это будет Python, то там структура чуть-чуть сложнее даже двусвязного списка, хотя точных подробностей я не знаю. В любом случае, делать иной тип списка — только когда все заработает и когда профайлер скажет, что все тормоза именно в перестановках.

shimon ★★★★★
() автор топика
Ответ на: комментарий от shimon

Профайлер, ИМХО, нужно смотреть на обработке данных, близких к реальным. И опять мы возвращаемся к вопросу, о вероятности того, что нескольно подряд идущих писем подходящих под одно правило.

Наверное, можно ещё для каждого письма определять на каком правиле по счёту оно срабтало и определять среднее для последних 10 и 100 писем. И уже на этом основании сортировать список.

mky ★★★★★
()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.