?

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:
 
 
 
(Anonymous) on July 18th, 2009 04:04 pm (UTC)
А.Кипчатиов: вопросы по алгоритму
Павел!

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

Сначала то, что мне не понятно.
1. Фраза загадка: "Если есть более одного tier1 не подряд, скорее всего, имеем route leak, и считаем известными лишь отношения до первого tier1 и после последнего." Просто не понял фразы. Лишь догадываюсь, что связей вниз, а потом вверх не бывает, если верх правильно определен, то их надо просто исключить? Об этом речь?

2. Почему и как для двух операторов А и B отношения будут определены после того, когда найдется путь через общего для них Tier1? А, если там ассиметрия, т.е. А отдает траф на Б, но берет его через С. А над всеми ими через разное количество хопов разные Тир1. Как связь с "точкой сборки" поможет определить отношения А-Б?
Тут я теряюсь в догадках вообще.

3. Алгоритм написан для повального пересчета всех маршрутов всех операторов или находит отношения для списка операторов, отыскивая лишь их связи?

4. Вообще много путей замыкается, не доходя до тирванов. На пирингах и на операторах агрегаторах. И чем дальше развивается провайдинг тем это явление заметнее. Поэтому возникает вопрос, можно ли построить график количества замыкания маршрутов ниже точки сборки на тирванах, скажем от количества хопов до тирванов?

5. А можно опубликовать список транзит-фри операторов по первому шагу алгоритма, например, для трех разных наборов данных с годовой разницей? Очень интересно, как изменяется этот список.

6. Павел, а вы оценивали разбросы результатов от одного файла данных к другому.

Павел и совсем простые вопросы.

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

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




Pavel Gulchouck: gulgul_kiev on July 18th, 2009 06:07 pm (UTC)
Re: А.Кипчатиов: вопросы по алгоритму
Спасибо за ваше внимание и вопросы.
Отвечу несколькими разными сообщениями.

> 1. Фраза загадка: "Если есть более одного tier1 не подряд, скорее всего, имеем route leak, и считаем известными лишь отношения до первого tier1 и после последнего." Просто не понял фразы. Лишь догадываюсь, что связей вниз, а потом вверх не бывает, если верх правильно определен, то их надо просто исключить? Об этом речь?

Допустим, тиерванами являются провайдеры 1, 2 и 3. Мы видим путь "100 101 1 102 103 2 104 105". То есть, присутствует два тиервана 1 и 2, но не подряд - между ними находятся автономки 102 и 103. В этом случае мы считаем, что 100 является клиентом 101, 105 - клиентом 104, а больше мы ничего не знаем, потому что где-то в районе 102-103, судя по всему, имеем роутлик.
Если же роутлик произошёд с одной стороны тиервана (например, в данном примере 104 является клиентом 2 и 105, и через него префикс от 105 сбежал на 2), то этот роутлик словится по тому, что таких путей будет намного меньше, чем тех, где 104 выступает как клиент 105, при анализе всей таблицы 104 будет признан клиентом 105, и в обработке этого пути префикс не будет включён в клиентский конус 104.
Re: А.Кипчатиов: вопросы по алгоритму - (Anonymous) on July 18th, 2009 08:05 pm (UTC) (Expand)
Re: А.Кипчатиов: вопросы по алгоритму - (Anonymous) on July 18th, 2009 08:10 pm (UTC) (Expand)
Re: А.Кипчатов: вопросы по алгоритму - (Anonymous) on July 18th, 2009 08:15 pm (UTC) (Expand)
Re: А.Кипчатов: вопросы по алгоритму - (Anonymous) on July 19th, 2009 01:23 am (UTC) (Expand)
Re: А.Кипчатов: вопросы по алгоритму - (Anonymous) on July 18th, 2009 08:27 pm (UTC) (Expand)
thomas_yk on July 22nd, 2009 07:58 am (UTC)
Вопросы
Присоеденяюсь к респектам :)
Хочу так же понять как строится рейтинг. Так своего рейтинга у меня нет, то вопросы будут дилетантскими :) (по крайней мере поначалу).

Начать хочу с попытки развернуть очевидность
"Очевидно, что если с какой-то точки более половины fullview видно по пути "a b с ...", a и b не могут быть tier1. А с - вполне может (если, конечно, не существует пути "a b с d ...", по которому видно более половины)."

Я понял данное предложение так:
Предполагаем что ни один из провайдеров не может отдавать на пире половину full-view. Отсюда делаем вывод что наличие одинакового пути для больше чем половины маршрутов говорит об устойчивой связи клиент-аплинк. Из этого следует что провайдеры a и b не могут быть tier1. Соответственно для каждого снимка с одного из источников определяется список устойчивых кусков as-path из которого затем ближайший к оригинатору префикса попадает в кандидаты на tier1.

Прально ?

Потом берется весь список кандидатов и по всем снимкам перебираются as-path по всем возможным вариантам связей кандидатов тройками. То есть берется три кандидата и ищутся все as-path где они идут подряд. Как происходит этот процесс ? то есть если встречается путь a b c как определить кто здесь лишний ?
Pavel Gulchouck: gulgul_kiev on July 22nd, 2009 11:37 am (UTC)
Re: Вопросы
По построению списка кандидатов - да, всё правильно.
Дальше - просматриваются все известные пути, и для каждой найденной тройки (точнее, цепочки длиннее двух) кандидатов у крайних увеличивается некий счётчик. Как бы его назвать... Пусть будет K. :) Количество всех путей, в которых встречается кандидат - N.
Если найдены тройки кандидатовов, то из списка удаляется тот, у которого максимальный показатель K/N. После чего число К для оставшихся кандидатов пересчитывается и цикл повторяется.

Вообще-то алгоритм построения списка тирванов я сейчас пытаюсь модифицировать, потому что он мне не очень нравится.
Daniel Ginsburgdbg on August 8th, 2009 09:21 pm (UTC)
Правильно ли я понимаю, что предложенный алгоритм не пытается идентифицировать p2p линки кроме как между tier1'ами?
Pavel Gulchouck: gulgul_kiev on August 9th, 2009 05:13 am (UTC)
Если мы в каких-то путях видим линк между A и B, но в путях с tier1 он ни разу не встречается, этот линк считается пиринговым.
Иными словами, алгоритм вообще не пытается, видя путь без tier1, строить предположения о том, где в этом пути какие отношения.
Кроме того, если в пути только один tier1, его отношения с ближайшими соседями тоже не считаются определёнными - они могут быть как c2p, так и p2p. Если этот линк ни разу не встречается в путях с двумя tier1 - значит, это пиринг.
Основное предположение, на которое опирается алгоритм - что отношение c2p хотя бы с одной из точек будет видно через tier1, и потому все клиентские префиксы будут включены в клиентский конус апстрима. Даже если у апстрима 80% трафика ходит через пиринги, и даже если апстрим сам является tier1. Алгоритм может учесть префикс и по пути без tier1, если там отношения между автономками в пути определены однозначно и не вызывают сомнений, но это уже несущественная деталь.
Если через tier1 видны как отношения A->B, так и B->A (взаимный бэкап или роутлик), их отношения считаются неопределёнными и считаются для каждого префикса отдельно, только по путям, в которых присутствуют tier1.
(no subject) - gul_kiev on August 9th, 2009 05:43 am (UTC) (Expand)
(no subject) - dbg on August 9th, 2009 08:36 am (UTC) (Expand)
(no subject) - gul_kiev on September 4th, 2009 01:33 pm (UTC) (Expand)
ext_157634 on February 1st, 2010 12:23 pm (UTC)
Пустые строки
Спасибо за рейтинг.
Вопросик
Присутствуют в табличке , в частности и наша AS48658 , почти пустая - ни названия , ни страны.

AS создана больше года назад ... думаю база у Вас обновляется чаще ... или реже , или это у нас касяк , или у вас?

спасибо большое.
Pavel Gulchouck: gulgul_kiev on February 1st, 2010 12:38 pm (UTC)
Re: Пустые строки
Таблица с названиями автономок и их принадлежности странам, к сожалению, автоматически (пока) не обновляется. Она взята с caida.org, после чего туда эпизодически руками вношу изменения и добавления (как правило, если в top1000 оказываются неизвестные автономки).
Сейчас добавил информацию про AS48658, спасибо.
(Anonymous) on March 2nd, 2010 07:06 am (UTC)
Спсиок провайдеров
Павел, добрый день.
Вопрос следующий: почему в вашем рейтинге присутствуют далеко не все провайдеры? Например, по Узбекистану у Вас был учтён лишь Uztelecom (а сегодня и он куда-то пропал - по зоне uz вообще ничего нет), а AS там гораздо больше:
Intal Telecom JV AS 28910
ASN of "Uzbektelecom" Joint-Stock Company AS 34250
BGP ASN of TEXNOPROSISTEM Ltd AS 34718
National Data Network Company "UzPAK" AS 8193
The AS of CJSC "Sharq Telekom" AS 31203
Sarkor-Telecom is an ISP in Uzbekistan, AS 12365
OOO "Net City" AS 42654
AS of BUZTON J.V. - fixed line telecom operator in ... AS 29385
Uzbek Scientific & Education Network AS 31492
RADIO-MSU AS 8756
ISP "Ars-Inform" AS 42017
И др.
Та же ситуация и по другим странам СНГ - практически нет ни провайдеров ни рейтинга.
Есть ли возможность дополнить Ваши таблицы?
Pavel Gulchouck: gulgul_kiev on March 2nd, 2010 07:28 am (UTC)
Re: Спсиок провайдеров
Наверное, вы смотрите первую тысячу - а это считается по мировому рейтингу. Скажите показывать первые 100000, тогда будут показаны все провайдеры.
Дополнять можно, но только в ручном режиме (через меня). Буду благодарен за уточнение информации.

Практически все перечисленные вами провайдеры в списке были, только AS28910, AS31203 и AS8756 были отнесены к другим странам (что для двух последних неудивительно - в их объектах RIPE страна нигде не указана).
Для AS28910 поправил, спасибо, для AS31203 и AS8756 я вижу московские контакты и пока не могу отнести их к узбекским провайдерам. Дайте пруфлинк на их принадлежность Узбекистану.

AS31203:

role: Trans Group Holding Contact Role
address: Officce 320&322, 4-th block, 17/2 Selskokhozyaystvennaya str.,
address: Moscow, 129226, Russian Federation

AS8756:

role: RADIO-MSU Network Operations Center
address: Radio-MSU NOC
address: Nuclear Physics Institute
address: Moscow State University
address: 119899 Moscow
address: Russia
phone: +7 495 9328880
phone: +7 495 9395877
fax-no: +7 495 9328974
remarks: trouble: -----------------------------------------------------------
remarks: trouble: Radio-MSU NOC is reachable 09:00-21:00 on MSK working days.
remarks: trouble: -----------------------------------------------------------
remarks: trouble: For problems with routing contact (5 x 12):
remarks: trouble: Radio-MSU Network Operation Center:
remarks: trouble: - noc@radio-msu.net
remarks: trouble: - +7 495 932-88-80
remarks: trouble: - +7 495 939-58-77
remarks: trouble: -----------------------------------------------------------
Re: Спсиок провайдеров - (Anonymous) on March 2nd, 2010 08:15 am (UTC) (Expand)
Re: Спсиок провайдеров - gul_kiev on March 2nd, 2010 08:41 am (UTC) (Expand)
Re: Спсиок провайдеров - (Anonymous) on March 2nd, 2010 09:03 am (UTC) (Expand)
Re: Спсиок провайдеров - (Anonymous) on March 2nd, 2010 08:37 am (UTC) (Expand)
Re: Спсиок провайдеров - gul_kiev on March 2nd, 2010 08:57 am (UTC) (Expand)
(Anonymous) on May 3rd, 2010 07:43 am (UTC)
Добрый день. Спасибо за вашу работу.
В БД райпа четко указна принадлежность AS31252 к Молдове. Не подскажете почему данная АС появляется в списке операторов Украины?
Pavel Gulchouck: gulgul_kiev on May 10th, 2010 04:52 am (UTC)
Поправил, спасибо.
(Anonymous) on November 26th, 2010 02:48 pm (UTC)
Поломалось?
Updates/Withdr/WithdrRate по нулям
сильно тормозит.
Pavel Gulchouck: gulgul_kiev on November 26th, 2010 04:05 pm (UTC)
Работает, вроде.
То, что updates/withdr по нулям - да, это что-то поломалось на route-views.org, там с 21-го ноября почему-то нет апдейтов, только рибы. Написал им.
Тормозит - ну что ж поделать. Сейчас исходного материала примерно 600G, в обработанном виде в sql база 20G.
Подумаю, как можно ускорить.
(no subject) - gul_kiev on February 7th, 2011 08:44 am (UTC) (Expand)
(no subject) - gul_kiev on November 26th, 2010 07:12 pm (UTC) (Expand)
(no subject) - (Anonymous) on November 27th, 2010 08:13 pm (UTC) (Expand)
аплинки по нулям - (Anonymous) on December 29th, 2010 11:57 am (UTC) (Expand)
Re: аплинки по нулям - gul_kiev on December 29th, 2010 04:18 pm (UTC) (Expand)
(Anonymous) on February 28th, 2011 09:32 am (UTC)
SQL-server error, try later
Поломалось? Сегодня с утра по кнопке "build rank table" вместо таблички выдаёт сабж :(
Pavel Gulchouck: gulgul_kiev on February 28th, 2011 09:58 am (UTC)
Re: SQL-server error, try later
Действительно, спасибо.
Починил.
Re: SQL-server error, try later - (Anonymous) on February 28th, 2011 11:10 am (UTC) (Expand)
(Anonymous) on April 16th, 2011 04:43 pm (UTC)
14 апреля
Поломалось? после 14 апреля no data found
gul_techgul_tech on May 8th, 2011 08:30 pm (UTC)
Re: 14 апреля
Действительно, поломалось, пока я в отпуске был, сорри.
Примерно 28-го апреля починил.
Спасибо.