1. Если вы только начинаете программировать на ассемблере и не знаете с чего начать, тогда попробуйте среду разработки ASM Visual IDE
    (c) на правах рекламы
    Скрыть объявление

Протоколы маршрутизации. AntNet.

Тема в разделе "WASM.NETWORKS", создана пользователем l_inc, 8 дек 2010.

  1. l_inc

    l_inc New Member

    Публикаций:
    0
    Регистрация:
    29 сен 2005
    Сообщения:
    2.566
    Добрый день всем, кому было не лень заглянуть в эту тему. :-)
    На данный момент, насколько мне известно, наиболее распространён OSPF.
    Но есть такой не особо известный алгоритм роутинга AntNet (не link-state, не distance-vector). Было проведено достаточно много исследований, которые показали, что он очень круто (по сравнению с другими алгоритмами) справляется с балансировкой загрузки сети и при определённой доработке ни разу не уступает OSPF в скорости адаптации к изменениям в её топологии.
    В общем, вопрос в основном к тем, кто слышал об AntNet. Алгоритм был предложен более десяти лет назад. Если он настолько крут, то почему он нигде не используется? Десять лет — мало? Или есть какие-то скрытые причины?
     
  2. l_inc

    l_inc New Member

    Публикаций:
    0
    Регистрация:
    29 сен 2005
    Сообщения:
    2.566
    На случай, если кто-то вдруг забредёт сюда в поисках ответа.
    Причин оказалось немало. Основная в том, что при неперегруженной сети средняя задержка пакетов неслабо превышает задержку OSPF. Кроме того, он не особо приспособлен к отказам маршрутизаторов (хотя отказ соединений явным образом обрабатывается в модификации AntHocNet), не рассчитан на иерархические сети и не содержит средств аутентификации узлов (хотя в OSPF v3 от неё тоже отказались в пользу нативной IPv6). А что протокол будет делать в несвязной сети, вообще неясно. Не уверен в его способности додуматься до no route to host.
    А насчёт хорошей балансировки... да очень высокая сравнительная пропускная способность и низкие потери пакетов при сильных нагрузках, особенно в модификации AntNet-FA, но есть и другие алгоритмы вроде BeeHive, дающие сходную пропускную способность при более низких задержках пакетов.
    В общем, как-то вот так вот.
     
  3. shshs

    shshs New Member

    Публикаций:
    0
    Регистрация:
    18 янв 2011
    Сообщения:
    8
    По поводу протоколов маршрутизации. Не считая BGP, который Pilicy Based Path Vector - то есть хорош благодяря политикам которые может настраивать каждый провайдер, он ведет себя как distance vector, так вот....есть 2 основных типа - link state и distance vector. Если знакомы с фракталами - есть еще qspn (для проекта p2p сетей netsukuku.freaknet.org).

    К сожалению, из общедоступных distance vector есть только RIP. EIGRP проприетарный цискин, хотя дает наиболее лучшие показатели сходимости, использует DUAL алгоритм. RIP в серьезных сетях не используют, EIGRP простой и прекрасный протокол. Если бы EIGRP не был проприетарен - готов поспорить это был бы самый популярный протокол!

    Из distance vector - OSPF и IS-IS. Надо понимать, что принципиальное отличие link-state от vector протоколов в том, что роутер в link-state хранит информацию о всех маршрутизаторах в заданном домене (арии, линк-топологии в случае IS-IS), в момент инициализации маршрутизаторы синхронизируют эту информацию (Link-State DataBase - LSDB) и если что-то меняется то меняется LSDB каждого роутера в домене. Как только LSDB синхронизирована (то есть когерентна LSDB каждого роутера в арии) происходит расчет маршрутов, запускается SPF алгоритм и обновляется таблица маршрутизации. Наибольшая проблема link-state протоколов это именно SPF - он критичен, то есть занимает довольно много времени и непосредственно влияет на сходимость сети! Есть его более легкая версия Partial Route Calculation (PRC), это по сути поиск маршрута в списке, но для OSPF'а так считаются только External маршруты и Inter-area.

    Не стоит недоценивать IS-IS. Хоть в его основе лежит все тот же SPF, именно его выбирают преимущественно в MPLS сетях как IGP - основная причина это то что для IP префиксов он использует PRC (для самого IS-IS нужна CLNS OSI адресация), то есть он легче OSPF'а.

    Внимание вопрос. Если векторные протоколы быстрее link-state (а это так), то зачем тогда link state? Если IP маршрутизация per-hop behaviour, то есть только каждый последующий маршрутизатор в пути решает куда бросить данный пакет, то есть вы не можете выбирать путь прохождения пакета или потока через заданную цепочку маршрутизаторов на начальном роутере, путь определяется каждым!!! роутером в цепочке. Зачем маршрутизатору в домене знать всю LSDB, а не только маршруты соседей (как в векторных протоколах)??? Я к тому, что в IP сети информации, которую собирают distance-vector протоколы вполне достаточно для маршрутизации. И зачем тогда SPF если DUAL гораздо быстрее.

    Ответ очевиден только для MPLS сетей с возможностью Traffic Engineering, то есть когда маршрутизация осуществляется по-сути на первом, входном (ingrees LSR - label switch router) маршрутизаторе для потока по заданным характеристикам. Только там использование link-state протоколов имеет смысл. В остальных случаях надо по возможности юзать векторные.

    я все сказал
     
  4. l_inc

    l_inc New Member

    Публикаций:
    0
    Регистрация:
    29 сен 2005
    Сообщения:
    2.566
    shshs
    Неясно только, к чему это всё было. Не говоря уже о том, что многое просто неверно.
     
  5. shshs

    shshs New Member

    Публикаций:
    0
    Регистрация:
    18 янв 2011
    Сообщения:
    8
    >На данный момент, насколько мне известно, наиболее распространён OSPF.
    это по поводу сказанного
    И что, простите не верно?
     
  6. l_inc

    l_inc New Member

    Публикаций:
    0
    Регистрация:
    29 сен 2005
    Сообщения:
    2.566
    shshs
    Начиная с того, что OSPF и IS-IS каким-то чудом названы distance-vector при том, что единственный доступный distance-vector — RIP (с ходу могу назвать ещё DBF, Q-R и PQ-R). Кстати, упомянутый EIGRP — далеко не классический distance-vector, а скорее гибридный. И заканчивая тем, что distance-vector протоколы "работают быстрее" link-state. Distance-vector могут эффективно использоваться в малых сетях на десяток-полтора роутеров. Внутри больших AS используют OSPF из-за крайне низкой скорости конвергенции distance-vector протоколов к кратчайшим путям при изменении топологии сети.
    Но защищать свою точку зрения я не буду, т.к. нет ни времени, ни желания разводить длительные споры. Можете считать меня голословным.
    P.S. Если есть что сказать по теме (AntNet или хотя бы другие nature-inspired алгоритмы), то милости просим.
     
  7. shshs

    shshs New Member

    Публикаций:
    0
    Регистрация:
    18 янв 2011
    Сообщения:
    8
    Опечатка, это же очевидно. Конечно Link-state.
    Может с ходу и назовете еще оборудование на котором эти протоколы реализованы?
    Не путайте RIP, которому диаметр максимум 15 хопов. EIGRP ведет себя намного конвергентней OSPF (single area) на диаметрах в сотню роутеров. Конечно, для OSFP и IS-IS максимальное кол-во маршрутизаторов 1000-2000. Даже крупные операторы, типа Orange, Level 3 не имеют такого значительного кол-ва роутеров в одном домене. По поводу больших AS. Дело не в кол-ве роутеров (в современном мире), а в кол-ве префиксов. Так вот чем больше префиксов тем хуже OSPF'у "сходиться".
     
  8. l_inc

    l_inc New Member

    Публикаций:
    0
    Регистрация:
    29 сен 2005
    Сообщения:
    2.566
    shshs
    Честно говоря, без понятия. На момент создания темы в мою задачу входило поковырять информацию о разных протоколах с упором на AntNet, чтобы выявить какой-то, дающий среднюю задержку пакетов сходную OSPF'овской, но при этом значительно лучше рапределяющий нагрузку на сеть, увеличивая тем самым общую пропускную способность, особенно в условиях близких к сатурации. Упрощённо говоря, мне нужна была информация о применимости, а не о применённости протоколов.
    Не хуже. Просто роутерам нужно больше памяти и более мощные вычислительные способности. А вот distance-vector протоколам это не поможет в улучшении их сходимости.
     
  9. shshs

    shshs New Member

    Публикаций:
    0
    Регистрация:
    18 янв 2011
    Сообщения:
    8
    Задержку каких пакетов??? Если вы говорите о Hello, механизма Neighbour и Adjacency discovery, то у каждого реализованного протокола есть таймеры, которые можно менять, у того же OSPF как и у IS-IS можно выставить Hollo interval меньше секунды.

    Распределять нагрузку на сеть это вообще не задача конкретного протокола маршрутизации. Есть Load balancing (equal cost, unequal cost), но там все статически, то есть текущее состояние канала, как и загруженности маршрутизатора в целом не проверяется.

    Протокол маршрутизации никак не увеличивает пропускную способность, он не для этого создан.

    В общем, я говорю о том что реально проверено на практике, не только теория FSM конкретного протокола. Основная характеристика протокола в конкретной реализации является сходимость. Так вот сходимость зависит от многих факторов. Если вы Control Plane дизайнер, могу порекомендовать ресурсы, где описывают практическое применение и реализацию протоколов люди которые их пишут для конкретного железа.
     
  10. l_inc

    l_inc New Member

    Публикаций:
    0
    Регистрация:
    29 сен 2005
    Сообщения:
    2.566
    shshs
    Эх... я знал, что если начну отвечать, одним постом это не закончится.
    Как каких? Основных пакетов данных. Payload-пакетов, а не собственных hello. Какого пользователя вообще интересуют внутренние проблемы протокола? В задачу протоколов маршрутизации (пм) входит не абы-как доставлять пакеты данных, а с кратчайшей задержкой. Поэтому средняя задержка пакета — это едва ли не основной показатель, характеризующий пм.
    Это не задача OSPF. А в общем случае крайне желательное свойство, которое так же входит в список важных показателей пм. Именно поэтому и продолжают придумывать новые пм вроде AntNet или BeeHive, которые нацелены именно на улучшение балансировки загрузки (в случае OSPF payload-пакеты будут идти через "быстрое" соединение, забивая его до отказа, а параллельное чуть-чуть более медленное будет пустовать).
    Это в известных Вам протоколах статически. А уже больше десяти лет, как пытаются придумывать протоколы с динамической адаптацией под загрузку сети и конкретных соединений. И, кстати, довольно успешно.
    Для справки: существуют не только алгоритмы кратчайших путей (которые и подразделяются на distance-vector и link-state), существуют ещё алгоритмы оптимального роутинга (общесетевой направленности), существуют статические и адаптивные, распределённые и централизованные.
    Аналогично. Известные Вам не увеличивают.
    Вы знаете, что означает сходимость сама по себе? По определению это время необходимое для того, чтобы протокол начал принимать стабильные решения маршрутизации при стабилизации топологии, т.е. данный роутер для данного назначения будет всегда выбирать данный линк, если топология будет постоянна. Так вот сама по себе сходимость никого не интересует. То, что себе там протокол быстро сошёлся на неизвестно чём, не важно до тех пор, пока следствием этой сходимости не станет минимальная задержка payload-пакета либо, как конкурирующее и достаточно важное свойство — максимальная пропускная способность. Некоторые протоколы вообще никогда не сходятся до конца.
     
  11. shshs

    shshs New Member

    Публикаций:
    0
    Регистрация:
    18 янв 2011
    Сообщения:
    8
    А вы о сферических конях в вакууме, не знал простите.

    Спешу вас огорчить. Сейчас протокол маршрутизации (пм) уже не краеугольная задача современной науки. Еще алгоритмы и модели, придуманные в далекие 50ые никто толком реализовать не может. Сейчас не в балансировки вопрос, а скорее в скорости мигания лазера и приемника, способного с такой частотой работать, оптоволокно не используется и на процент от того что может предложить. К тому же вычислительные мощности еще не настолько велики, чтобы хотя бы пакетики принимать и обрабатывать, не говоря уже о данных на таких скоростях.

    Задача решена коммутацией лямбд волны света, GMPLS называется.

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

    Сходимость протокола, это время от момента изменения состояния сети (которое способно повлиять на изменение маршрутов) до момента приобретения когерентного состояни всеми участниками, которые определяют этот маршрут. Когерентное на практике значит либо LSDB синхронна, либо вектор расчитан. На практике это время от момента изменения в сети до момента установки (отмены) соответствующих маршрутов в таблицу маршрутизации. Сама таблица (Control Plane) по сути является данными для программирования Forwarding Plane, ASIC'ов, в которых содержатся данные для правильной MAC (L2) коммутации пакетов. В это время входит и время работы (пускай даже относительное - вы же знаете как расчитывается сложность алгоритмов) алгоритмов маршрутизации, к примеру DUAL и SPF. Очень важно именно НА чем данный протокол сошелся, потому как задержку привносит никак не протокол сам по себе, а оборудование (с очередями, CPU мощностями) и линиями передачи, задержку которых вы никаким протоколом не измените.

    Поверьте, важно именно это, а не сферические кони в вакууме.
     
  12. l_inc

    l_inc New Member

    Публикаций:
    0
    Регистрация:
    29 сен 2005
    Сообщения:
    2.566
    shshs
    Может потому, что они неудачно придуманы в свете их практической применимости?
    Так об этом же и речь. Поясняю... Общая задержка при передаче пакета от одного хоста к другому состоит из четырёх компонентов: propagation delay, transmission delay, processing delay, queueing delay. В случае оптических линий узким горлышком является сумма последних двух. Предположим, что роутер 1 может выбрать путь к роутеру 4 через быстрый роутер 2, а может выбрать через тормозной роутер 3. OSPF будет выбирать всегда роутер 2, переполняя его очереди при высокой нагрузке (мало того, роутер 2 просто начнёт выкидывать пакеты, что будет приводить к повторной передаче на уровне вышележащего TCP, что будет приводить к ещё большим нагрузкам). Тогда как балансирующий пм будет учитывать перегрузки, пуская некоторые пакеты через роутер 3. А теперь скажите мне, каким боком здесь Ваши оптические кабели?
    По-моему очевидно, что под доставкой пакета в контексте пм имеется в виду выбор маршрута, а не контроль целостности или повторная передача. Так что у меня и ноги на месте, и голова между ними не болтается.
    Любой протокол будет сферическим конём в вакууме, пока не начнёт применяться на практике. Соответственно вполне можно было бы и знать, прочитав первый пост темы.
     
  13. shshs

    shshs New Member

    Публикаций:
    0
    Регистрация:
    18 янв 2011
    Сообщения:
    8
    Скоре потому что есть реалии действительности. Те же модели теории временных рядов адекватны для сетей достаточно большого масштаба, это не корпорации, а скорей операторы межрегиональные.

    Для этого существует так называемый Traffic Engineering, который уже давно не новость. Да и протокол типа Resource Reservation (RSVP) решает подобные проблемы, а никак не протокол маршрутизации.
     
  14. l_inc

    l_inc New Member

    Публикаций:
    0
    Регистрация:
    29 сен 2005
    Сообщения:
    2.566
    shshs
    Надоело спорить, кто решает какие проблемы. :-) ПМ, балансирующие нагрузку, не просто существуют в прошлом, а продолжают придумываться (наверное, не просто так). Это факт. Я не могу спорить с человеком, который игнорирует факты.
     
  15. shshs

    shshs New Member

    Публикаций:
    0
    Регистрация:
    18 янв 2011
    Сообщения:
    8
    Факты на моей стороне, а то о чем вы говорите даже гуглится с трудом.
     
  16. l_inc

    l_inc New Member

    Публикаций:
    0
    Регистрация:
    29 сен 2005
    Сообщения:
    2.566
    shshs
    И на том спасибо. :-) А то создалось впечатление, что и не пытались вовсе. В духе: я знаю, что знаю, а что не знаю, того нет.
     
  17. shshs

    shshs New Member

    Публикаций:
    0
    Регистрация:
    18 янв 2011
    Сообщения:
    8
    Всегда полезно интересоваться чем-то новым или свежим я бы сказал. Теперь хоть буду представлять что такое AntNet. Я знаю в каком направлении движется индустрия, стандартизация и пр., где очень много всего завязано, и просто так отвергнуть всю предыдущую работу и сказать: "А теперь будем рулить как я сказал...". Уж каким бы вы гениальным не были....

    Так что на enterprise эта пустая трата времени. А локальные задачи вы можете решить уже существующим, будет гораздо ДЕШЕВЛЕ чем велосипед изобретать. Разве что вы на военку работаете, там денег не считают....