?

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:
 
 
 
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.
Pavel Gulchouck: gulgul_kiev on August 9th, 2009 05:43 am (UTC)
Btw, по каким критериям можно отличить роутлики от легитимных путей? Я понимаю, что формальных признаков нет (когда договорные отношения неизвестны), но хоть на чём строить эвристику - можете ли посоветовать что-то? Я пока рассматриваю пути и туплю. Количество путей в ту и другую сторону - не подходит, убежавших путей может быть больше, чем настоящих путей на нерадивого клиента. Вес провайдеров - зависит от того, какие отношения принять между ними. Длина as-path - довольно опасный критерий: в тех роутликах, что я рассматривал, иногда нерадивый клиент имеет прямой линк на tier1. И при этом нужно не забывать, что роутлик бывает через пиринговый линк (когда встречных путей нет), и что бывает взаимный бэкап...
Daniel Ginsburgdbg on August 9th, 2009 08:36 am (UTC)
Ну, собственно, complex policy, т.е. отношения, не классифицируемые в терминах p2p, c2p, p2c, s2s, принципиально не отличимы от route leak. Они отличаются только тем, специально или не специально это сделано :)

Есть две задачи:
1) выделять случаи complex policy
2) отличать их от route leak

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

А вот первая задача сложнее. В http://www.caida.org/publications/papers/2006/as_relationships_inference/, они мутят грязное - вводят коэффициент в критерии оптимизации MAX2SAT-проблемы и потом подбирают его на глаз, основываясь на том, насколько "правдоподобным" выглядит top5 в решении. Ничего удивительного, что никакой разумной интерпретации полученные результаты не поддаются.
Pavel Gulchouck: gulgul_kiev on September 4th, 2009 01:33 pm (UTC)
Спасибо.
Применил следующий алгоритм - на вид работает.
Между каждыми двумя взаимодействующими AS A и B формируем некую величину уверенности sure, что A является апстримом для B для некоторых префиксов. Эта величина считается отдельно в каждую сторону, то есть может быть одновременно, что A является апстримом для B для одних префиксов, и B является апстримом для A для других. Либо же наоборот - никто ни для кого не апстрим (если это p2p). Значения sure: 0 - путей от A до B, когда B апстрим, не замечено; 1 - замечены пути только без tier1, уверенности нет; 2 - замечены пути до tier1, но не более того; 3 - можно с определённой степенью уверенности сказать, что хотя бы для каких-то префиксов это не роутлик; 4 - судя по всему, B является одним из основных апстримов для A; -1 - судя по всему, это роутлик.
Эти значения sure определяются за несколько этапов (проходов):
1. Строим отношения между AS, основываясь на путях, в которых есть Tier1. Если есть отношения в разные стороны, помечаем как complex. Если по одну сторону от Tier1 есть A-B, считаем, что A является апстримом для B с уверенностью sure=2. Если при этом A и B входят в одну группу, считаем sure=3 (предполагаем отношения s2s - внутри группы роутлики маловероятны).
2. Если префикс виден по пути A>B более чем с половины точек наблюдения, значит, это не лик (ставим sure=3). Тут я основываюсь на том, что, во-первых, роутлики обычно длиннее, чем валидные пути, а во-вторых, если бóльшую часть интернета клиент видит кривым путём, это будет очень быстро исправлено (и на рейтинг такой путь не повлияет, потому что сильно выпадающие из общей картины данные отбрасываются).
3. Если собственные префиксы A видны через B, а собственные префиксы B не видны через A, значит, путь B>A - не лик (sure=3). За собственными префиксами провайдеры обычно следят более внимательно, чем за транзитными, транзитные убегают несравнимо чаще.
4. Если больше половины собственных префиксов A видны через B, а никакие собственные префиксы B не видны через A (рассматривая только пути без complex relations), то B является апстримом для A (sure=4).
5. Если B->A sure==4, A->B sure==2, и для префикса есть пути как ...->A->B->...->tier1, так и ...->A->...tier1 (без B), значит, A->B - leak (sure=-1). Иными словами, апстрим может купить у своего клиента доступ для какой-то отдельной сетки (complex relations), но он не будет покупать у клиента айпитранзит для префикса, которому он сам может обеспечить (и обеспечивает) доступ. Это роутлик.
6. Пересчитываем отношения заново; для путей, для которых в обратную сторону sure>=3 и в эту сторону sure!=4, либо если в обе стороны sure==2 - не строим отношения client-upstream по ту сторону tier1, где есть этот complex, начиная за один шаг от него (A->B->C?D->...->tier1 -> only A->B, but not B->C, MB p2p).
7. Если в пути нет tier1, но он выглядит нормально (сначала несколько c2p, потом несколько p2c, и по пути возможны p2p), то p2p-линки, стоящие между двумя c2p, помечаем как c2p (sure=1). Аналогично - стоящие между двумя p2c помечаем как p2c. Если в итоге (после прохода) отношения получились не complex, а определёнными (с sure==1) - ориентируемся на них при построении клиентских конусов.

Роутликом считаем путь, в котором после p2c следует c2p. Последний из p2c-хопов перед c2p или p2p помечаем как route-leak.

Наибольшая путаница возникает за счёт s2s-линков. Потому что они явно отличаются от p2p (связь используется для ip transit), собственные сети могут быть видны в обе стороны - в общем, если не считать их единой AS, разобраться в таких линках и отличить s2s от route-leak очень трудно. Пока ограничился тем, что линки внутри явно заданных групп считаю s2s.

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