?

Log in

 
 
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 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: -----------------------------------------------------------
(Anonymous) on March 2nd, 2010 08:15 am (UTC)
Re: Спсиок провайдеров
Про AS31203 и AS8756 Вы видимо правы - пруфлинков у меня нет. Про первую 1000 тоже - спасибо за подсказку - мне дали ссылку на Вашу статистику совсем не давно - ещё не успел до конца разобраться, как ей пользоваться.
Вот, что у меня ещё есть по СНГ(в своё время собирал - буду рад, если пригодится):
Узбекистан (кроме уже отправленного):
ISP "Ars-Inform" AS 42017
?47452 AS 47452
JV "UNITECH" AS 30728
iPlus Ltd. AS 43060
BGP ASN of ISP East Telecom AS 39032
Lit-Tel LLC AS 47141
LLC "SERV​IS-KOMMUNIKATSIYA SISTEMALARI" AS 47752
Unitel AS 41202
ISP - Amaliy Aloqalar Biznesi Ltd., Tashkent, Uzbekistan AS 25389
FE Uzdunrobita Ltd AS 34871
Coscom - mobile and internet services AS 44748

Армения:
FiberNet AS 41965
Armenia Telephone Company AS 12297
Cornet-AM Closed Joint Stock Company AS 33852
AM NIC AS 8226
XALT LLC AS 31166
ADC - Armenian Datacom Company AS 42109
Yerevan Physics Institute AS 12304
Netsys JVC Autonomous System Yerevan, Armenia AS 21104
Crossnet LLC AS 39863
SoftLink LLC AS 48111
iCON Communications CJSC AS 8932
UCOM LLC AS 44395
Harmony Information Technologies and Education Development ... AS 48008
Clearstream Armenia CJSC AS 47414
Hi-Tech Gateway LLC AS 43845
Bionet Ltd. AS 42991
Linuxoid ISP AS 42209
Harknet LLC AS 48110
Institute for Informatics and Automation Problems of ... AS 47623
SatGate AS 30721
Vivacell AS 43733
Epygi Technologies AS 44001
Armenian Card (ArCa) CJSC AS 42688
AATVC CJSC AS 48333
Firmplace AS 47642
Interglobe AS 48244
Shirak Technologies Enterprise AS 44153
KV Net AS 47822
Скоро добавлю ещё Грузию и Азербайджан...
Pavel Gulchouck: gulgul_kiev on March 2nd, 2010 08:41 am (UTC)
Re: Спсиок провайдеров
Спасибо.
По Узбекистану 41202,43060,47141,47752 - поправил (были ошибочно отнесены к России, в их объектах страна явно не указана);
По Армении 42991 - поправил (была отнесена к России), 8932 - добавил (она вообще отсутствовала).
AS30721, насколько я вижу, относится к Литве, а не к Армении.
Остальные были прописаны корректно.

Btw, из каких источников вы берёте эти данные?

Насчёт ограничения на кол-во показываемых автономок - 100000 прописывать не обязательно, 0 означает unlimit (я просто сам забыл об этом).

Если у вас будут ещё дополнения и поправки к списку AS, думаю, лучше их присылайте приватно или на email .
(Anonymous) on March 2nd, 2010 09:03 am (UTC)
Re: Спсиок провайдеров
Доступа к источнику, где я это брал, к сожалению у меня уже нет... Так что теперь вся надежда на Вас)
(Anonymous) on March 2nd, 2010 08:37 am (UTC)
Re: Спсиок провайдеров
Грузия:
CCS AS 20771
United Telecom AS 35805
Egrisi JSC. AS 34797
Caucasus Network Tbilisi, Georgia AS 28751
Railway Telecom AS 41877
Wanex ltd. AS 15491
SANET NETWORK (AS) AS 12497
MAGTICOM AS 25249
LUNET LLC AS 47921
MOBITEL AS 41738
NamioNet AS 39441
Geonet AS 21214
T-NET AS 44327
GEOCELL AS 42082
"Global-Erty" JSC AS 34666
CDN AS 24997
GRENA AS 20545
Telecom Georgia AS 42806
Vtel-Georgia AS 44877
LLC Serviceline AS 47697
Service AS 35076
CTS LTD AS 43755
Maxtel Network Tbilisi, Georgia AS 39452
Project-service Ltd AS 47810
Bank of Georgia AS 48393

Азербайджан (тут только десятка лидеров, наверное все у Вас есть...)
Delta Telecom LTD. AS 29049
AzEuroTel AS 13099
"SMART SISTEMZ TECHNOLOJI" MMM AS 34876
Azeronline Information Services AS 15723
Az.StarNet LLC AS 39397
Bakinternet ISP, Azerbaijan AS 28787
Azerbaijan Telecomunication ISP AS 34170
Ultel LLC AS 39280
AZERIN AS 8814
Uninet Internet Service Provider AS 39232

Чем смог:)
Pavel Gulchouck: gulgul_kiev on March 2nd, 2010 08:57 am (UTC)
Re: Спсиок провайдеров
Спасибо.
Где были неточности - поправил.
Насчёт AS44877 непонятно - называется Vtel-Georgia, контакты в Иордании. В моей базе (взятой с caida.org) она отнесена к Иордании.