| 0 |
|
На июльском симпозиуме ACM (Association for Computing Machinery) по принципам распределенных вычислений сотрудники группы Theory of Distributed Systems Массачусетского технологического университета (MIT) представили новый матаппарат для анализа спонтанных (ad hoc) сетей – коммуникационных сетей, автоматически создаваемых беспроводными устройствами.
Прежние попытки теоретического анализа сетей ad hoc в большинстве своем исходили из предположения, что коммуникационные связи между устройствами стабильны, что далеко не всегда осуществимо в реальных ситуациях. «Они слишком сильно зависели от специфических допущений, принятых в модели, – подчеркнула профессор Нэнси Линч (Nancy Lynch), возглавляющая Theory of Distributed Systems Group. – Из-за этого алгоритмы становились нереалистичными и уязвимыми».
Разработанная в MIT модель позволяет принимать во внимание хаотические флуктуации пропускной способности соединений между элементами беспроводной сети (WLAN). Используя ее, ученые установили теоретические пределы эффективности распространения информации в подобных сетях и описали новые алгоритмы для достижения максимальной продуктивности их работы.
Адекватно реализовать фактор «хаотичности» в своей модели Линч и ее коллегам удалось, формально представив флуктуации качества связи в звеньях цепи как сознательные манипуляции гипотетического «противника». Он не может контролировать абсолютно все связи – часть из них продолжает функционировать, но способен варьировать пропускную способность остальных. При этом проектировщик сети не знает заранее, какие соединения надежны, а какие – нет.
В первой статье, вышедшей два года назад, был рассмотрен вариант с очень серьезным «противником»: он был способен предугадывать каждое решение по маршрутизации сообщений во всех узлах сети. Тогда было показано, что при таком наихудшем сценарии эффективные коммуникации становятся невозможны.
В новой статье «противник» значительно ослаблен. Он может точно знать как функционирует коммуникационный алгоритм, но должен планировать свои манипуляции заранее, до того как алгоритм приступит к работе. Даже в таком, редуцированном варианте, он более разрушителен, чем любые помехи, ожидающие беспроводные сети в реальном мире, такие как открывание и закрывание дверей, работающие микроволновые печи или идущий дождь.
В поиске стратегий сохранения контроля над функционированием сетей ученые исследовали два способа распространения сообщений. Для ситуации, когда один узел пытается транслировать сообщение всем остальным узлам сети, было установлено, что эффективные коммуникации возможны даже в присутствии «противника».
Другой, наиболее близкий к реальности сценарий, предполагал, что множество узлов передают сообщения, и каждый из их ближайших соседей должен получать сообщения, по меньшей мере, от одного передатчика. Было установлено, что «противник» способен подавлять работу таких сетей, но только если они имеют характерную структуру, при которой центральный узел соединяется со множеством соседних, не связанных между собой.
Такой тип сети маловероятен в реальном мире: если два устройства находятся на расстоянии уверенной связи с третьим, то они в большинстве случаев способны установить и прямое соединение друг с другом. При добавлении в модель соответствующего допущения – что два устройства, подключенные к третьему, могут иногда обмениваться информацией между собой – эффективные коммуникации становятся возможными.
Наиболее эффективно противостоящие «противнику» коммуникационные протоколы использовали элемент случайности. Они задавали для каждого узла вероятность передачи в каждом цикле коммуникаций (отрезке времени, требующемся для отсылки узлом сообщения ближайшим соседям). Таким образом, каждое отдельное сообщение характеризовалось уникальной последовательностью вероятностей. Кластеры узлов назначали временных лидеров, координирующих вероятности для локальных передатчиков. Исследователи MIT показали, что затрачиваемые на все это вычислительные ресурсы не оказывают существенного воздействия на скорость функционирования WLAN.
Ready, set, buy! Посібник для початківців - як придбати Copilot для Microsoft 365
| 0 |
|
