МуравьеНет

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

Профессор биологии Дебора Гордон (Deborah Gordon) изучала поведение муравьев на протяжении более 20 лет. Однажды она наблюдала, как рабочие муравьи таскали пищу в муравейник и ВНЕЗАПНО заметила, что насекомые каким-то образом кооперируются и находят кратчайшие пути к местам, где пища имеется и невероятным образом не ходят туда, где пищи нет. Дебора подключила к наблюдению своего приятеля Balaji Prabhakar (не смог написать это имя на русском), профессора компьютерных наук и эксперта по протоколам передачи данных. Поначалу Balaji Prabhakar не обнаружил ни одного пересечения между его работой и наблюдениями профессора Гордон, но вскоре совпадения нашлись. С отчетом можно ознакомиться (Осторожно, Моск!).

«На следующий день мне пришло в голову: «Оу, погодите! Это почти то же самое, что и IP — каждый муравей это, по сути, пакет, который может прийти не в том порядке, в котором был отправлен, оказаться повреждёнными (обычно повреждённые пакеты уничтожаются) или не прийти вовсе!» (муравьев, копирующих себя при передаче в процессе экспериментов обнаружено не было). 🙂

При этом любого муравья, ушедшего из муравейника, можно сравнить с ICMP Echo-Request, а его возвращение (или невозвращение) — это Echo-Reply. Если ушедший в определенном направлении муравей (направление муравьи помечают специальными феромонами прямо на земле) не вернулся, следовательно, в указанном направлении ходить не стоит — пищи нет, а то и опасность подстерегает. С другой стороны, если пакет (муравей) вернулся, да еще и с ништяком, то в ту сторону ходить не только можно, но и нужно.

О разметке феромонами путей следования муравьев и оптимизации маршрутов известно давно (правда, сравнивать с TCP/IP начали недавно) — даже имеются несколько алгоритмов решения задач класса «Путь коммивояжера», которые так и называются: «муравьиные алгоритмы» или «ant colony optimization». Вот, например, компьютерная симуляция интеллекта муравьев по переносу «муравьиных кладбищ» (красные точки, переходящие в области) подальше от входа в муравейник (красно-желтый круг)

Видео можно использовать в качестве медитации.

{youtube}rsqsZCH36Hk&feature{/youtube}

Совершенно логично, что при использовании логики ICMP (отправка и прием пакетов/муравьев) используются процедуры старта и процедуры завершения обмена данными муравьями.

Для старта используется в буквальном смысле Slow Start and Congestion Avoidance из RFC-5681: делается массовая рассылка пакетов (муравьев во все стороны) с целью найти какие-либо пути и определить пропускную способность каналов (в каком направлении надо искать). По тому, как, и с какой интенсивностью муравьи возвращаются в муравейник, колония может принимать различные решения: «большинство пакетов вернулось с такого-то направления, следовательно, в той стороне есть что-то и надо в основном идти туда».

Раз есть старт процесса, должно быть и его завершение, которое очень похоже на time out: «в течение 20 минут не вернулся ни один пакет муравей, следовательно, внешняя среда агрессивна (идет дождь, например) — закупорить выходы!». Что интересно, Time-To-Live является переменной величиной, зависящей от температуры воздуха — чем холоднее, тем меньше время ожидания «истечения времени». Такой подход позволяет колонии переходить в ночной режим более оптимально.

По сути, разработчики Интернет-протоколов, сами того не ведая, разработали алгоритмы, которые муравьи используют уже миллион лет. Хотя, возможно и ведали — множество современных вещей открыто в результате наблюдения за живой природой, самые известные, например, репейник — прототип застежки-липучки, или соломинка, как прототип конструкции высотных зданий. Теперь ждем реализации алгоритмов DDoS в исполнении муравьев, методики сокращения джиттера на основе наблюдения за пчелами, или реализации протоколов anycast по математике общения дельфинов. Ждем.

NAG.RU