Рейтинг провайдеров - описание алгоритма и софт
Итак, главная задача при построении рейтинга провайдеров - по таблицам маршрутизации понять, кто чей клиент.
Задача кажется примитивной (все, кто виден через 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
Софт (и перловая, и сишная версии) доступен вот здесь:
cvs -d :pserver:anonymous@happy.kiev.ua:/cvs co asrank
Пожелания по модификации алгоритма и по тому, какую ещё статистику имеет смысл считать, принимаются с благодарностью.
Задача кажется примитивной (все, кто виден через 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
Софт (и перловая, и сишная версии) доступен вот здесь:
cvs -d :pserver:anonymous@happy.kiev.ua:/cvs co asrank
Пожелания по модификации алгоритма и по тому, какую ещё статистику имеет смысл считать, принимаются с благодарностью.