Конференція Високопродуктивні обчислення, Київ, 13-15 жовтня 2014

Мурахи відкрили алгоритм TCP набагато раніше за людей

28 серпня 2012

Дослідники Стенфордського університету (США) виявили, що червона американська мураха-жнець (Pogonomyrmex barbatus) обирає, скільки особин слід надіслати за їжею приблизно так само, як інтернет-протокол TCP дізнається, скільки трафіку доступно для передачі даних. Дослідники назвали це явище «антернет» (anternet, від слова «ant» – «мураха»).

Червона американська мураха-жнець

Червона американська мураха-жнець або Бородата мураха-жнець – вид мурах, розповсюджених у Північній Америці, який має одну з найсильніших отрут серед усіх комах. Сила укусу цієї мурахи більша, ніж у шершня та медоносної бджоли. Як і у інших мурах-жнеців, основним кормом є насіння рослин.

За комахами спостерігала біолог Дебора Гордон, порівняти поведінку мурах з алгоритмом TCP спало на думку професору комп'ютерних наук Баладжи Прабхакар.

Transmission Control Protocol (TCP) являє собою алгоритм, який виконує обов’язки регулювальника на «перехрестях» Інтернет-потоків. Завдяки йому Мережа за лічені роки виросла з кількох десятків до мільярдів вузлів. Працює він наступним чином. Джерело (А) надсилає файл у пункт призначення (Б), причому файл розбивається на кілька пакетів. При отриманні кожного пакету Б надсилає відповідне повідомлення (ack) на адресу А.

Зворотній зв’язок необхідний для запобігання перенавантаженням. Якщо повідомлення приходить повільніше, ніж надсилаються дані, значить, пропускна здатність знизилась, а надсилати дані слід повільніше. В іншому випадку джерело збільшує швидкість передачі даних.

Виявляється, червоні мурахи поводять себе аналогічним чином. Швидкість, з якою мурахи відправляються за їжею, відповідає швидкості надходження продовольства. Фуражир не повернеться до гнізда, поки не знайде харч. Якщо в околицях багато насіння, женці повертаються швидше, в такому випадку до них приєднується все більше мурах. Якщо розвідники починають повертатись з порожніми лапками, конвеєр уповільнюється або навіть зупиняється.

Професор Прабхакар написав алгоритм для прогнозування поведінки мурах в залежності від кількості їжі (тобто пропускної здатності), і він виправдав себе. «Мурахи виявили цей алгоритм мільйони років тому», – резюмує спеціаліст.

Цікаво, що комахи знають й про дві інші фази TCP. Одна з них відома під назвою «повільний старт»: спочатку джерело надсилає велику порцію пакетів, щоб виміряти пропускну здатність. Саме таким чином мурахи спочатку відправляються на пошуки їжі великою групою.

Інший алгоритм, «тайм-аут», використовується, коли зв’язок порушується і джерело припиняє передачу пакетів. Якщо фуражири не повертаються до гнізда протягом 20 хвилин, надсилання нових розвідників припиняється.

Професор Прабхакар відмічає, що це відкриття поведінки мурах було зроблене ще у 70-х роках минулого століття і, можливо, вплинуло на творців Інтернет. Можливо, мурахи знають інші секрети, які допоможуть нам удосконалити Мережу. При цьому мурашині алгоритми повинні бути простими, розподіленими та масштабованими – як раз те, що нам зараз і потрібно.

Результати досліджень опубліковано у журналі PLoS Computational Biology.

Теги: TCP, мережа, пропускна здатність

Матеріали за темою:

Коментарі