Разговор о маршрутизации не окончен

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

Как известно, дистанционно-векторный протокол RIP (Routing Information Protocol) обладает рядом недостатков, ограничивающих его применение в автономных системах. Протокол OSPF (Open Shortest Path First), использующий алгоритм состояния связей, устраняет эти изъяны настолько эффективно, что работа кажется идеальной. На самом же деле существует серьезная проблема, с которой не могут справиться ни OSPF, ни тем более RIP.

Рис. 1.

Представьте себе фрагмент сети, изображенный на рис. 1. Буквами обозначены маршрутизаторы, а рядом с каждой линией связи указана ее метрика. Конкретные значения не балуют разнообразием, но они выбраны одинаковыми для того, чтобы проблему было проще понять. Очевидно, что, формируя маршрут от A к E, и RIP, и OSPF выберут путь AFGE. Маршрут через узлы B, C и D будет отвергнут, как более длинный. Теперь представим себе, что с узла H на узел I пересылаются большие объемы данных. Это приведет к тому, что пакет, переданный с A и адресованный E, будет поставлен в хвост длинной очереди на передачу сначала на узле F, а потом и на G. В сложившейся ситуации маршрут ABCDE оказался более предпочтительным, но используемые в настоящее время протоколы не позволяют обнаружить этот факт.

Существующие алгоритмы оптимизации потоков с учетом перегрузок каналов достаточно сложны, поэтому поиски более простых и эффективных методов решения этой задачи ведутся до сих пор. Одному из них и посвящен следующий материал.

Решение подсказывают... муравьи

Рис. 2.

Вряд ли уместно на страницах компьютерного журнала подробно рассматривать результаты, полученные биологами, изучающими поведение муравьев, пчел и других «коллективных» насекомых. Тем не менее один из экспериментов все же заслуживает нашего внимания. Предположим, что на пути от муравейника к источнику пищи встречается развилка и муравей должен самостоятельно выбрать один из двух путей (рис. 2). (Запретить муравью двигаться «по бездорожью» – нетривиальная задача, но при наличии определенной изобретательности ее можно решить.) Как видно, один из них намного длиннее, но муравей, находящийся на развилке, естественно, не имеет об этом никакого представления. Однако через некоторое время оказывается, что «муравьиный трафик» направлен именно по короткому пути. Как же это происходит?

Предположим наихудший вариант: самый первый путешественник, дойдя до развилки, выбирает длинный путь. Муравей помечает дорогу, выделяя вещества, которые называются феромонами – они, в частности, помогают найти обратный путь, выполняя роль зарубок, оставляемых охотником в лесу. Второй, дойдя до развилки, чувствует запах феромонов и чаще всего выбирает путь, уже проторенный его сородичем. Если бы все муравьи вели себя совершенно одинаково, то короткий путь был бы для них уже закрыт – все ориентировались бы по запаху и шли за пищей по длинной дороге. Однако в муравьином сообществе всегда есть особи, которым не чужд дух исследований. И вовсе не исключено, что такой, не признающий догм, первопроходец все же рискнет пойти по неизведанному пути и повернет туда, где до него еще никто не ходил. Теперь у следующего муравья выбор уже сложнее: либо следовать по длинной дороге, где до него ходили многие, либо по короткой, где прошел всего один муравей и запах относительно слабый. Не беда, если он снова выберет традиционный маршрут. Все равно вероятность использования альтернативного постепенно увеличивается, так как феромоны постепенно испаряются, а муравьи, возвращающиеся по короткуму пути, успевают «обновить» метки.

Каждый муравей, выбравший короткий путь, существенно повышает шансы, что по этому пути пойдут и его последователи. Срабатывает механизм положительной обратной связи и в конце концов основной поток переключается с длинной дороги на короткую. Таким образом, традиции муравейника делают благое дело, сокращая расстояние до пищи, а отдельные «исследователи», выбирающие путь, по которому почему-то никто не ходит, просто остаются ни с чем.

Наблюдения за живой природой часто приводят к интересным техническим решениям. Так произошло и на этот раз: именно муравьи подсказали Марко Дориго (Marco Dorigo) и Гианни Ди Каро (Gianni Di Caro) идею создания системы маршрутизации на базе мобильных агентов, которая получила название AntNet.

Мобильные агенты

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

Главная особенность, отличающая мобильные агенты от других типов программ, – это их способность перемещаться по сети, причем по собственной инициативе. По этой причине мобильными агентами нельзя считать ни апплеты, ни сценарии в составе HTML-страниц, ни даже сериализуемые объекты, допускающие копирование по сети (хотя отличия последних от мобильных агентов уже минимальны). На каком-то этапе своего выполнения агент решает, что для него имеет смысл сменить «место жительства». Он инициирует свое движение и на узле назначения продолжает работу в том же состоянии, в котором находился перед началом перемещения.

Очевидно, для написания агента подходит лишь язык, обеспечивающий реальную переносимость кода. Предпринимались неоднократные попытки реализации мобильных агентов на интерпретируемых языках, в частности Tcl, но, конечно же, бесспорным лидером в этой области остается Java. И еще один немаловажный факт. Какие бы блестящие решения не принимал разработчик, каким бы удачным не был выбор языка, мобильный агент не появится на том узле, где его не ждут. В противном случае вся сеть очень скоро будет наводнена вирусами, созданными по этому принципу. Переместиться мобильный агент может лишь на то устройство, где есть инфраструктура поддержки агентов данного конкретного типа, реализуемая порой достаточно сложными программами.

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

AntNet

Вступление было столь длинным, что о самой системе осталось сказать очень немного. Элементы AntNet, конечно же, включают непременный атрибут любого маршрутизатора – таблицу маршрутизации. Однако ее содержимое интерпретируется совсем не так, как на узлах, поддерживающих привычные протоколы RIP или OSPF. Запись в таблице – отнюдь не догма при выборе пути, а лишь некая вероятностная характеристика того или иного маршрута. Соответственно, их выбор не является жестко детерминированным.

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

Достигнув пункта назначения, агент прекращает свое существование, предварительно породив собственную «зеркальную копию». «Зеркальную» в том смысле, что перед агентом-двойником стоит прямо противоположная задача – попасть на исходный маршрутизатор. Справиться с ней довольно просто: достаточно лишь проделать в обратном порядке путь, описанный в стеке, составленном предшественником.

Дождавшись этого агента, маршрутизатор получает необходимую информацию о времени прохождения различных участков. Имеющиеся данные можно интерпретировать как реальную метрику пути, учитывающую текущую конфигурацию и загрузку сети. Сведения, поступившие от различных агентов, позволяют достаточно точно сравнить стоимость прохождения пакета по разным маршрутам и, соответственно, заполнить таблицу.

За все надо платить

Принцип определения маршрутов, применяемый в системе AntNet, обеспечивает движение пакетов по различным направлениям с учетом реальной загрузки линий. Но, увы, новое качество достается не бесплатно. Приходится смириться с резким увеличением накладных расходов, связанных со сбором информации о сети. Это не удивительно, поскольку приходится передавать исполняемый код агента. Да и объем данных о маршрутах увеличивается – ведь агент движется к узлу назначения отнюдь не по кратчайшему пути. Одним словом, AntNet создает нагрузку на сеть в 20–30, а в некоторых случаях – и в 40 (!) раз боóльшую, чем маршрутизаторы, поддерживающие протокол OSPF. Однако не следует пугаться этих ошеломляющих показателей. Несмотря на многократное повышение накладных расходов, данные, передаваемые AntNet, занимают приблизительно 0,3% пропускной способности линий связи, а это вполне приемлемая величина, в особенности если учесть положительный эффект от использования системы.

А нужны ли агенты?

Потеря 0,3% полезного ресурса – не катастрофа, но обязательно ли с ней мириться? Не стоит ли искать пути снижения накладных расходов? И, похоже, они найдутся, если включить информацию о маршрутах в состав IP-пакетов. Фантастика? Да, если мыслить категориями IPv4. Вполне реально, если принять к рассмотрению IPv6.

Как известно, в версии 6 протокола IP пакет может иметь несколько заголовков: основной и дополнительные. Один из последних – Routing Header – позволяет указать список узлов, через которые пакет должен пройти до места назначения. Другими словами, этот заголовок вполне может выполнять те же функции, что и стек агента AntNet.

Работа маршрутизатора (пока гипотетического) будет выглядеть следующим образом. На первом этапе устанавливаются исходные, пусть неоптимальные, маршруты. Они нужны лишь для того, чтобы начать работу в сети. Затем маршрутизатор приступает к передаче полезных данных – IP-пакетов. Их следует разделить на две категории. К первой отнесем те пакеты, которые предполагают подтверждение. В них, конечно же, помещаются данные, передаваемые средствами TCP – они составляют более 90% сетевого трафика. Ко второй причислим пакеты, направляемые «в один конец», например, инкапсулирующие дейтаграммы UDP.

Вторая категория неперспективная и задача маршрутизатора – как можно быстрее избавиться от таких данных – передать их по известным маршрутам. Первая же категория вполне подходит для целей сбора информации. Дополнительные заголовки (скажем, Hop-by-Hop Options Header) позволяют записать различные полезные сведения, например, время, проведенное в очереди или требуемое для передачи пакета. Для него также необходим идентификатор – подобную роль может с успехом выполнить метка потока (поле Flow Label основного заголовка IP). Все эти характеристики, конечно же, должны записывать и проверять промежуточные маршрутизаторы, а на узле назначения формируется пакет с подтверждением, включающий все собранные сведения.

Количество пакетов, которыми узлы сети обмениваются в процессе реальной работы, чрезвычайно велико. Благодаря этому появляется возможность определить параметры различных участков сети гораздо точнее, чем посредством специализированных пакетов маршрутизации или мобильных агентов, которые передаются сравнительно редко.

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

Интернет работает, причем вполне надежно, но это не означает, что его структура идеальна. Сети ждут смелых экспериментаторов. И, как сказано в заголовке статьи, разговор о маршрутизации еще не окончен...

Ready, set, buy! Посібник для початківців - як придбати Copilot для Microsoft 365