?

Log in

No account? Create an account
 
 
16 July 2009 @ 11:26 am
Рейтинг провайдеров - описание алгоритма и софт  
Итак, главная задача при построении рейтинга провайдеров - по таблицам маршрутизации понять, кто чей клиент.
Задача кажется примитивной (все, кто виден через AS13249, являются клиентами IT Systems, и т.д.) только на первый взгляд. Проблема в том, что, если есть путь, скажем, "9002 35320 12593", не так просто понять, является ли 35320 (ETT) клиентом 9002 (ReTN), или это пиринг, или 9002 покупает IP-транзит у 35320. Последнее предположение кажется абсурдным для людей, которые знают ситуацию на рынке ISP, но этого не знает программа, ведь именно эти данные она и должна выдать как результат. В этой цепочке взаимоотношения между 35320 и 12593 для программы тоже непонятны.

При построении рейтинга на Caida исходили из (в целом, справедливого) предположения о том, что в нормальном случае в as-path сначала путь идёт от клиентов к апстримам ("наверх"), потом, возможно, один пиринговый линк (но не более одного), и далее - от апстримов к клиентам ("вниз"). В противном случае (например, апстрим-клиент-апстрим, т.е. винз-вверх, либо пиринг-вверх-вниз, либо вверх-пиринг-пиринг и все прочие варианты) что-то не так: либо мы неправильно понимаем, кто чей клиент, либо это route leak, т.е. результат ошибочной конфигурации роутера, когда кто-то передаёт через себя чужой трафик (не принадлежащий его клиентам). Caida сформулировала задачу формально-математически: сделать граф роутинга направленным так, чтобы количество некорректных маршрутов было минимальным. Задача оказалась сложной, формально неразрешимой, была применена эвристика. В частности, если от изменения направления клиент-апстрим на каком-то линке количество некорректных путей не меняется, принимают, что более мелкий провайдер является клиентом более крупного, а более крупным считается тот, у кого больше прямых линков с другими AS. То есть, например, если IT Systems взаимодействует с RTComm на DE-CIX, и у IT Systems прямых линков (мелких клиентов, паритетов) больше, чем у RTComm, то RTComm будет считаться клиентом IT Systems. Если меньше - наоборот. В итоге, не знаю уж, из-за ошибки алгоритма или реализации, в итоговой таблице у них получился мусор: полностью одинаковый набор клиентов (почти весь Интернет) у примерно сотни провайдеров, включая многие украинские и российские, и в пределах этой группы места распределились в соответствии с Degree, т.е. количеством прямых линков. Они делали попытки определять p2p-линки, но, судя по результатам, не очень успешно.

Прежде всего, расскажу, что запутывает схему и усложняет задачу. Во-первых, взаимодействие между двумя AS могут быть сложнее, чем пиринг (p2p) или клиент-апстрим (с2p). Взаимоотношения могут быть разными в разных точках присутствия и для разных префиксов. Например, p2p во Франкфурте и c2p в Киеве. Во-вторых, может быть взаимный бэкап. В-третьих, бывает платный пиринг, либо покупка доступа к части Интернета (к UA-IX или к MSK-IX).

Я для определения отношений между AS исходил, прежде всего, из топологии Интернета, а именно: что существует несколько Tier1, у которых нет ни одного апстрима, и между которыми есть пиринг каждый с каждым. Первая фаза обработки - построение списка таких Tier1. Тут термин "Tier1" понимается топологически, а не административно, то есть, в список вполне могут попасть те, кто имеет платный пиринг с некоторыми "настоящими" tier1. Очевидно, что если с какой-то точки более половины fullview видно по пути "a b с ...", a и b не могут быть tier1. А с - вполне может (если, конечно, не существует пути "a b с d ...", по которому видно более половины). Так сначала строится список кандидатов в tier1, потом, учитывая невозможность пути "... a b c ...", где a, b и c - tier1, из этого списка постепенно удаляются те, кто "не вписывается" (возможность роутликов у самих tier1 отбрасываем). Тут тоже всё происходит не совсем гладко, например, "не вписался" Savvis из-за путей "3356 6453 3561", присутствующих у всего двух префиксов /23. Но в целом, список получается очень близок к истине, то есть, там нет никого лишнего (не имеющего пиринг со всеми остальными), а от того, что кто-то из tier1 в этот список не попал, результаты рейтинга зависят совсем не существенно (дальше будет понятно, почему).

Вторая фаза: построение взаимоотношений между AS. А именно: если в as-path есть два tier1 рядом, то все отношения известны: вся цепочка до первого tier1 - от клиента к апстриму, после второго - от апстрима к клиенту. Если в пути только один tier1, то неизвестны его отношения с ближайшими соседями (c2p или p2p), но известно всё остальное. Если есть более одного tier1 не подряд, скорее всего, имеем route leak, и считаем известными лишь отношения до первого tier1 и после последнего.

Таблицы собираются более чем с сорока роутеров в мире, подключенных к совершенно разным провайдерам в разных странах. Поэтому, если A является клиентом B, практически наверняка хотя бы с одной из этих точек путь к A будет виден через одного из tier1, и взаимоотношения между A и B будут определены. Если B сам является tier1, хотя бы из одной точки A будет виден через другого tier1 (по пути "... tier1 B A"), и отношения тоже будут определены. Тем не менее, если из N определённых взаимодействий между A и B совпадают менее 90%, взаимодействие считается неопределённым.

Далее - собственно подсчёт статистики. Для каждого пути находится первая валидная связь апстрим-клиент ("валидная" - то есть, после которой в пути уже нет связей клиент-апстрим), и начиная с неё префикс добавляется ко всем AS. То есть, например, в пути "a-b>c-d<e-f" (b является клиентом c, e - клиентом d) префикс добавляется в клиентский конус d, e и f. Таким образом, роутлики оказываются отброшены из статистики.

Вот, собственно, и всё.

Сначала была написана перловая версия обработчика. Но она была (естественно) жутко неэффективной как по времени обработки, так и по используемой памяти. У меня в планах - обработка истории, построение графиков, интерфейс в виде cgi, а обработать все старые таблицы перловым скриптом за разумное время нереально, поэтому пришлось делать сишную версию, которая оказалась на порядок (может, на два - не мерял) более эффективной как по скорости выполнения, так и по памяти.


Софт (и перловая, и сишная версии) доступен вот здесь:
cvs -d :pserver:anonymous@happy.kiev.ua:/cvs co asrank

Пожелания по модификации алгоритма и по тому, какую ещё статистику имеет смысл считать, принимаются с благодарностью.
Tags:
 
 
 
Pavel Gulchouck: gulgul_kiev on July 18th, 2009 06:36 pm (UTC)
Re: А.Кипчатов: вопросы по алгоритму
> 3. Алгоритм написан для повального пересчета всех маршрутов всех операторов или находит отношения для списка операторов, отыскивая лишь их связи?

Для повального. Потом отдельным скриптом из этих общих результатов делается выборка по российским/украинским провайдерам.

> 7. Сколько времени требуется алгоритму, чтоб выдать данные по первой тысяче?

На двухгигагерцовом пне

> 8. Сколько Вы потратили времени от первоначальной идеи взяться за эту задачу до первых удовлетворительных результатов.

3-5 дней. Потом - причёсывание, оптимизация и т.п.
Pavel Gulchouck: gulgul_kiev on July 18th, 2009 07:11 pm (UTC)
Re: А.Кипчатов: вопросы по алгоритму
Сорри, забыл вписать время, когда программа закончит обработку.
Вот что получилось при обработке одного снимка (бинарная таблица RIB на 642M), сишная программа:
real 3m48.119s
user 0m57.591s
sys 0m2.191s
(Anonymous) on July 18th, 2009 08:15 pm (UTC)
Re: А.Кипчатов: вопросы по алгоритму
А что это за части?
Каждая работает 1 раз?
Если так, то это 5 минут. Я ожидал на порядок больше почему-то.
Это обнадеживает.
Pavel Gulchouck: gulgul_kiev on July 18th, 2009 08:29 pm (UTC)
Re: А.Кипчатов: вопросы по алгоритму
Нет, не суммируется, ещё лучше.
user - "чистое" время занятости процессора выполнением задачи
sys - время выполнения системных вызовов
real - общее время, прошедшее от запуска до завершения, включая время ожидания внешних событий (в первую очередь, готовности диска), время выполнения других процессов на той же машине и пр.
На порядок (или на два) больше у перловой версии.
Ну и это время обработки всего лишь одного снимка, а этих снимков есть 12 штук за каждый день. В сумме за несколько лет набирается ого-го. У меня получилось, если один файл обрабатывается 4 минуты, файлы за один год - более 12 суток, а этих лет несколько. И это, к тому же, без учёта времени разархивации.
(Anonymous) on July 19th, 2009 01:23 am (UTC)
Re: А.Кипчатов: вопросы по алгоритму
огромное спасибо за проделанную работу! очень интересная статистика.
я могу помочь с компьютерными мощностями для обработки имеющихся данных существующим алгоритмом или для обсчёта ещё чего-нибудь, что хотелось бы сделать, но мало мощностей.
если интересно, свяжитесь со мной - ICQ 8025844, rojer9@gmail.com
Pavel Gulchouck: gulgul_kiev on July 19th, 2009 12:33 pm (UTC)
Re: А.Кипчатов: вопросы по алгоритму
Спасибо за предложение.
Моя идея в том, чтобы однократно обработать все таблицы, и какие-то результирующие данные по ним сохранить в sql. Чтобы это была однократная ресурсоёмкая задача, а потом строить всякие графики, статистики и т.п. можно было уже по этим обобщённым данным из sql.
Для начала нужно чётко понять, какую информацию нужно собрать и сохранить, чтобы её было, с одной стороны, достаточно (чтобы не пришлось через неделю обрабатывать все исходные данные заново, для получения новых данных), а с другой - чтобы результирующий размер был разумным (в идеале - пригодным для online-обработки из cgi по запросу). Как только с этим определюсь - возможно, обращусь за помощью по мощностям, ещё раз спасибо.