1. Новости
Заметки пользователей
29.08.2012 08:39
3834
0
29.08.2012 08:39
PDF
3834
0

Муравьенет

Автор: Wanderer From

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

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

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

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

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

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

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

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

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

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

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

0 комментариев
Оставлять комментарии могут только авторизованные пользователи